A089105 -id:A089105 - cp's OEIS frontend

A089825 Smallest n such that the least witness function W(n) = m, as m runs through the values in A089105.

9, 2047, 1373653, 134670080641, 25326001, 307768373641, 3215031751, 1502401849747176241, 2152302898747, 1478868544880821, 3034679039109989281, 3474749660383

Offset: 1

N. J. A. Sloane, Jan 18 2004

The least witness of 3825123056546413051 is 37, and no smaller number has 37 as its least witness. [Charles R Greathouse IV, Aug 14 2010]

			Comment from _Don Reble_, May 27 2014: The sequence begins:
2 9
3 2047
5 1373653
6 134670080641
7 25326001
10 307768373641
11 3215031751
12 1502401849747176241
13 2152302898747
14 1478868544880821
15 3034679039109989281
17 3474749660383
18 ?
19 4498414682539051
20 ?
21 ?
22 16043083915816662841
23 341550071728321

R. Crandall and C. Pomerance, Prime Numbers: A Computational Perspective, Springer, NY, 2001; see p. 157 (p. 168 in the second printing).

Cf. A089105.

a(8)-a(13) from Charles R Greathouse IV, Aug 14 2010

Corrected by Don Reble, May 27 2014

A007395 Constant sequence: the all 2's sequence.

Original entry on oeis.org

2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2

Offset: 1

N. J. A. Sloane

Continued fraction for 1 + sqrt(2). - Philippe Deléham, Nov 14 2006
a(n) = A213999(n,1). - Reinhard Zumkeller, Jul 03 2012
The least witness function W(k) is defined for odd composite numbers k. The sequence W(k) does not have its own entry in the OEIS because W(k) = 2 for all k with 9 <= k < 2047; then W(2047)=3. Cf. A089105. - N. J. A. Sloane, Sep 17 2014
a(n) = A254858(n-1,1). - Reinhard Zumkeller, Feb 09 2015
a(n) = number of permutations of length n+2 having exactly one ascent such that the first element the permutation is 2. - Ran Pan, Apr 20 2015
With alternating signs, this is the sequence of determinants of the 3 X 3 matrices m with m(i,j) = Fibonacci(n+i+j-2)^2. - Michel Marcus, Dec 23 2015
For p = prime(n+2), a(n) = ord_p(H_(p-1)), where ord_p denotes the p-adic valuation and H_i = 1 + 1/2 + ... + 1/i is a harmonic sum, except for n = 1944 and n = 157504, where ord_p(H_(p-1)) = 3, and any other term of A088164 that may exist (see Conrad link). The sequence a(n) = ord_p(H_(p-1)) does not have its own entry in the OEIS. - Felix Fröhlich, Mar 16 2016
This sequence is the only infinite bounded sequence of positive integers such that a(n) = (a(n-1) + a(n-2)) / gcd(a(n-1), a(n-2)) for all n >= 2. - Bernard Schott, Dec 28 2018

Titu Andreescu and Dorin Andrica, Number Theory, Birkhäuser, 2009, from 1999 Russian Mathematical Olympiad, p. 347.
Paulo Ribenboim, My Numbers, My Friends: Popular Lectures on Number Theory, Springer-Verlag, NY, 2000, p. 6.
N. J. A. Sloane and Simon Plouffe, The Encyclopedia of Integer Sequences, Academic Press, 1995 (includes this sequence).

25th All-Russian Mathematical Olympiad, Grade 10, Problem 2, p. 2, 1999.
Tobias Boege and Thomas Kahle, Construction Methods for Gaussoids, arXiv:1902.11260 [math.CO], 2019.
Keith Conrad, The p-adic growth of harmonic sums
Daniele A. Gewurz and Francesca Merola, Sequences realized as Parker vectors of oligomorphic permutation groups, J. Integer Seqs., Vol. 6, 2003.
R. H. Hardin, Binary arrays with both rows and cols sorted, symmetries
Tanya Khovanova, Recursive Sequences
Mihai Prunescu, On other two representations of the C-recursive integer sequences by terms in modular arithmetic, arXiv:2406.06436 [math.NT], 2024. See p. 18.
Mihai Prunescu and Lorenzo Sauras-Altuzarra, On the representation of C-recursive integer sequences by arithmetic terms, arXiv:2405.04083 [math.LO], 2024. See p. 16.
Mihai Prunescu and Joseph M. Shunia, On modular representations of C-recursive integer sequences, arXiv:2502.16928 [math.NT], 2025. See p. 5.
Aram Tangboonduangjit and Thotsaporn Thanatipanonda, Determinants Containing Powers of Generalized Fibonacci Numbers, arXiv:1512.07025 [math.CO], 2015.
Eric Weisstein's World of Mathematics, Hamiltonian Cycle
Dominika Závacká, Cristina Dalfó, and Miquel Angel Fiol, Integer sequences from k-iterated line digraphs, CEUR: Proc. 24th Conf. Info. Tech. - Appl. and Theory (ITAT 2024) Vol 3792, 156-161. See p. 161, Table 2.
Index to divisibility sequences
Index entries for recurrences a(n) = k*a(n - 1) +/- a(n - 2)
Index entries for linear recurrences with constant coefficients, signature (1).

Cf. A000004, A000012, A002061, A010701, A089105, A165900.

Cf. A213999, A254858.

a007395 = const 2
a007395_list = repeat 2  -- Reinhard Zumkeller, May 07 2012

Mathematica
```
Table[2, {105}]
```

makelist(2,n,0,30); /* Martin Ettl, Nov 09 2012 */

a(n) = 2 \\ Charles R Greathouse IV, Apr 07 2012

def A007395(n): return 2 # Chai Wah Wu, Nov 10 2022

G.f.: 2/(1-x), and e.g.f.: 2*e^x. - Mohammad K. Azarian, Dec 22 2008
a(n) = A000005(A000040(n)). - Omar E. Pol, Feb 28 2018
a(n) = A002061(n) - A165900(n). - Torlach Rush, Feb 21 2019

A341646 Numbers with a strictly superior squarefree divisor.

Original entry on oeis.org

2, 3, 5, 6, 7, 10, 11, 12, 13, 14, 15, 17, 18, 19, 20, 21, 22, 23, 24, 26, 28, 29, 30, 31, 33, 34, 35, 37, 38, 39, 40, 41, 42, 43, 44, 45, 46, 47, 50, 51, 52, 53, 55, 56, 57, 58, 59, 60, 61, 62, 63, 65, 66, 67, 68, 69, 70, 71, 73, 74, 75, 76, 77, 78, 79, 80

Offset: 1

Gus Wiseman, Feb 22 2021

nonn

We define a divisor d|n to be strictly superior if d > n/d. Strictly superior divisors are counted by A056924 and listed by A341673.
This is a subsequence of A007916, i.e., no perfect powers appear here. [For perfect powers n, a supposed strictly superior squarefree divisor d=p*q*r... with distinct primes p,q,r,s...  has a complementary divisor n/d=p^i*q^j*r^k*s*... with i,j,k>=1, so the complementary divisor is at least as large as d, a contradiction.] Entries in A007916 but not in here are 48, 54, 72, 96, 108, 160, 162, 192,... - R. J. Mathar, Jul 07 2023
Is this a duplicate of A089105? - R. J. Mathar, Jul 24 2023

			60 has three strictly superior squarefree divisors {10,15,30} so 60 is in the sequence.

Amiram Eldar, Table of n, a(n) for n = 1..10000

The version for prime instead of squarefree divisors is A064052.
The version for prime-power instead of squarefree divisors is the complement of A051283.
The weakly superior version is the complement of A059172.
The version for odd instead of squarefree divisors is A116883.
These are the positions of nonzero terms in A341595.
The complement is A341645.
A005117 lists squarefree numbers.
A038548 counts superior (or inferior) divisors.
A056924 counts strictly superior (or strictly inferior) divisors.
A140271 selects the smallest strictly superior divisor.
A207375 list central divisors.
A341673 lists strictly superior divisors.
- Inferior: A033676, A063962, A066839, A069288, A161906, A217581, A333749.
- Superior: A033677, A063538, A063539, A070038, A072500, A116882, A161908, A341591, A341592, A341593, A341675, A341676.
- Strictly Inferior: A060775, A070039, A333805, A333806, A341596, A341674.
- Strictly Superior: A048098, A238535, A341594, A341595, A341643, A341644.
Cf. A001222, A001248, A006530, A020639, A112798.
Subsequence of A007916.

isA341646 := proc(n)
    local d ;
    for d in numtheory[divisors](n) do
        if d>n/d then
            if issqrfree(d) then
                return true ;
            end if;
        end if;
    end do:
    false ;
end proc:
for n from 2 to 100 do
    if isA341646(n) then
        printf("%d,",n) ;
    end if;
end do: # R. J. Mathar, Jul 07 2023

Select[Range[100],Function[n,Select[Divisors[n],SquareFreeQ[#]&&#>n/#&]!={}]]

is(n) = fordiv(n, d, if(d^2 > n && issquarefree(d), return(1))); 0; \\ Amiram Eldar, Nov 01 2024

A006945 Smallest odd composite number that requires n Miller-Rabin primality tests.

Original entry on oeis.org

9, 2047, 1373653, 25326001, 3215031751, 2152302898747, 3474749660383, 341550071728321, 341550071728321, 3825123056546413051, 3825123056546413051, 3825123056546413051, 318665857834031151167461, 3317044064679887385961981

Offset: 1

N. J. A. Sloane

The tests are performed on sequential prime numbers starting with 2. Note that some terms are repeated.

Same as A014233 except for the first term.

			2047=23*89. 1373653 = 829*1657. 25326001 = 11251*2251. 3215031751 = 151*751*28351. 2152302898747 = 6763*10627*29947.

R. Crandall and C. Pomerance, Prime Numbers: A Computational Perspective, Springer, NY, 2001; see p. 157.
Paulo Ribenboim, The Little Book of Bigger Primes, Springer-Verlag NY 2004. See p. 98.
N. J. A. Sloane and Simon Plouffe, The Encyclopedia of Integer Sequences, Academic Press, 1995 (includes this sequence).

Joerg Arndt, Matters Computational (The Fxtbook)
Eric Bach, Explicit bounds for primality testing and related problems, Mathematics of Computation 55 (1990), pp. 355-380.
G. Jaeschke, On strong pseudoprimes to several bases, Math. Comp., 61 (1993), 915-926.
Yupeng Jiang, Yingpu Deng, Strong pseudoprimes to the first 9 prime bases, arXiv:1207.0063v1 [math.NT], June 30, 2012.
C. Pomerance, J. L. Selfridge and S. S. Wagstaff, Jr., The pseudoprimes to 25.10^9, Mathematics of Computation 35 (1980), pp. 1003-1026.
S. Wagon, Primality testing, Math. Intellig., 8 (No. 3, 1986), 58-61.
Zhenxiang Zhang and Min Tang, Finding strong pseudoprimes to several bases. II, Mathematics of Computation 72 (2003), pp. 2085-2097.
Index entries for sequences related to pseudoprimes

Cf. A089105, A089825.

Bach shows that, on the ERH, a(n) >> exp(sqrt(1/2 * x log x)). [Charles R Greathouse IV, May 17 2011]

Extended and description corrected by Jud McCranie Feb 15 1997.
a(10)-a(12) from Charles R Greathouse IV, Aug 14 2010
a(13)-a(14) copied from A014233 by Max Alekseyev, Feb 15 2017

A380978 Sequence of minimal Fermat witnesses for compositeness. a(n) is the least k such that the smallest composite number that is a Fermat pseudoprime to bases {a(i) : 1 <= i < n} is not a Fermat pseudoprime to base k.

Original entry on oeis.org

2, 3, 5, 7, 13, 11, 17, 41, 37, 19, 31, 43, 23, 53, 29, 101, 61, 109, 71, 67, 73, 113, 151, 89, 97, 211, 191, 157, 163, 193, 139, 281, 107, 103, 181, 47, 127, 271, 131, 307, 59, 257, 229, 331, 337, 199, 241, 461, 239, 617, 367, 263, 401, 251, 149, 421, 137, 277

Offset: 1

Jan Kostanjevec, Feb 10 2025

nonn

			For n = 1, a(1) = 2, since 2 is the first Fermat witness, proving the compositeness of 4.
For n = 2, a(2) = 3, since 3 is the next required Fermat witness, proving the compositeness of 341 (all previous composites are witnessed by 2).
For n = 3, a(3) = 5, since 5 is the next required Fermat witness, proving the compositeness of  1105 (all previous composites are witnessed by 2 and 3).

Eric Weisstein's World of Mathematics, Fermat Pseudoprime, Witness
Index entries for sequences related to pseudoprimes

Cf. A001567, A089105, A321790, A380979.

a(1) = 2, otherwise a(n) = A321790(k), where k is such that A001567(k) = A380979(n). - Peter Munn, Mar 12 2025

More terms from Jinyuan Wang, Mar 05 2025

cp's OEIS Frontend

A089825 Smallest n such that the least witness function W(n) = m, as m runs through the values in A089105.

Views

Author

Keywords

Comments

Examples

References

Crossrefs

Extensions

A007395 Constant sequence: the all 2's sequence.

Views

Author

Keywords

Comments

References

Links

Crossrefs

Programs

Haskell

Mathematica

Maxima

PARI

Python

Formula

A341646 Numbers with a strictly superior squarefree divisor.

Views

Author

Keywords

Comments

Examples

Links

Crossrefs

Programs

Maple

Mathematica

PARI

A006945 Smallest odd composite number that requires n Miller-Rabin primality tests.

Views

Author

Keywords

Comments

Examples

References

Links

Crossrefs

Formula

Extensions

A380978 Sequence of minimal Fermat witnesses for compositeness. a(n) is the least k such that the smallest composite number that is a Fermat pseudoprime to bases {a(i) : 1 <= i < n} is not a Fermat pseudoprime to base k.

Views

Author

Keywords

Examples

Links

Crossrefs

Formula

Extensions