A037202 -id:A037202 - cp's OEIS frontend

A244624 Consider the number of lines in the Pratt certificate for the n-th prime (A037202). This sequence shows where 2n first occurs.

1, 2, 4, 9, 14, 34, 61, 120, 215, 690, 1144, 2584, 5626, 13709, 31275, 63461, 145767, 340332, 649190, 1703684, 4218462, 10675070, 22892978

Offset: 0

Joerg Arndt and Robert G. Wilson v, Jul 02 2014

See comment section of A037202.

a(n) ~ 2*a(n-1).

Cf. A037202, A037231.

a[1] = 1; a[n_] := a[n] = 1 + Plus @@ (a@ PrimePi@# & /@ First /@ FactorInteger[ Prime@ n - 1]); k = 1; t = Table[0, {1000}]; While[k < 1000000000000001, If[a@ k < 1001 && t[[a[k]/2]] == 0, t[[a[k]/2]] = k; Print[{a@k, k}]]; k++]; t

Also PrimePi( A037231 ).

A037231 Primes which set a new record for length of Pratt certificate.

Original entry on oeis.org

2, 3, 7, 23, 43, 139, 283, 659, 1319, 5179, 9227, 23159, 55399, 148439, 366683, 793439, 1953839, 4875119, 9750239, 27353747, 71815607, 192287243, 430893643

Offset: 1

David W. Wilson

Eric Weisstein's World of Mathematics, Pratt Certificate.

Cf. A037202.

a[1] = 1; a[n_] := a[n] = 1 + Plus @@ (a@ PrimePi@ # & /@ First /@ FactorInteger[ Prime@ n - 1]); t = Table[ 0, {25}]; k = 2; While[k < 23420001, b = a[k]/2; If[b < 1001 && t[[b]] == 0, t[[b]] = Prime@ k; Print[{b, Prime@ k }]]; k++]; t

A034697 a(1)=1, a(n)= 1 + Sum a(p), p prime, p | n-1.

Original entry on oeis.org

1, 1, 2, 3, 2, 3, 4, 5, 2, 3, 4, 5, 4, 5, 6, 5, 2, 3, 4, 5, 4, 7, 6, 7, 4, 3, 6, 3, 6, 7, 6, 7, 2, 7, 4, 7, 4, 5, 6, 7, 4, 5, 8, 9, 6, 5, 8, 9, 4, 5, 4, 5, 6, 7, 4, 7, 6, 7, 8, 9, 6, 7, 8, 7, 2, 7, 8, 9, 4, 9, 8, 9, 4, 5, 6, 5, 6, 9, 8, 9

Offset: 1

N. J. A. Sloane

nonn

Suggested by Bach and Shallit, Algorithmic Number Theory, I, p. 270.

Cf. A037202.

A177803 The number of lines in the analog of Pratt primality certificate for the n-th semiprime.

Original entry on oeis.org

1, 2, 1, 2, 1, 2, 3, 4, 1, 3, 1, 2, 3, 2, 1, 4, 1, 5, 6, 7, 1, 3, 4, 5, 3, 3, 1, 7, 1, 2, 3, 4, 5, 5, 1, 2, 3, 5, 1, 8, 1, 8, 5, 6, 1, 3, 4, 7, 8, 6, 1, 4, 5, 3, 4, 5, 1, 8, 1, 2, 8, 2, 3, 10, 1, 5, 6, 9, 1, 5, 1, 2, 6, 3, 4, 8, 1, 5, 3, 4, 1, 9, 10, 11, 12, 8, 1, 9, 10, 7, 8, 9, 10, 3, 1, 5, 5

Offset: 4

Jonathan Vos Post, Dec 12 2010

			a (5) = 2 = 1 + a(4) because 4 | (5-1) and 4 = 2*2 is a semiprime.
a (6) = 1 because there is no semiprime that divides (6-1) = 5, a prime.
a (7) = 2 = 1 + a(6) = 1+1 because 6 | (7-1) and 6 = 2*3 is a semiprime.
a (8) = 1 because there is no semiprime that divides (8-1) = 7, a prime.
a (9) = 2 = 1 + a(4) = 1+1 because 4 | (9-1).
a(10) = 3 = 1 + a(9) = 1+2 because 9 | (10-1) and 9 is a semiprime.
a(11) = 4 = 1 + a(10) = 1+3 because 10 | (11-1) and 10 = 2*5 is a semiprime.
a(12) = 1 because there is no semiprime that divides (12-1) = 11, a prime.
a(13) = 3 = 1 + a(4) + a(6) = 1+1+1 because both 4 and 6 divide into (13-1) = 12 and are semiprimes.
a(14) = 1 because there is no semiprime that divides (14-1) = 13, a prime.
a(15) = 2 = 1 + a(14) = 1+1 because 14 | (15-1).
a(16) = 3 = 1 + a(15) = 1+2 because 15=3*5 is the only semiprime which divides 16-1.
a(17) = 2 = 1 + a(4) = 1+1 because 4 | (17-1) and 4 is the only such semiprime.

Alois P. Heinz, Table of n, a(n) for n = 4..1000

Cf. A001358, A037202.

a:= proc(n) option remember; 1 +add (`if` (not isprime(k) and add (i[2], i=ifactors(k)[2])=2 and irem (n-1, k)=0, a(k), 0), k=4..n-1) end: seq (a(n), n=4..100);  # Alois P. Heinz, Dec 12 2010

a[n_] := a[n] = 1 + Sum[If[!PrimeQ[k] && Total@FactorInteger[k][[All, 2]] == 2 && Mod[n - 1, k] == 0, a[k], 0], {k, 4, n - 1}];
a /@ Range[4, 100] (* Jean-François Alcover, Nov 20 2020, after Alois P. Heinz *)

a(4) = 1; a(n) = 1 + Sum a(k), k semiprime, k | n-1.

More terms from Alois P. Heinz, Dec 12 2010

cp's OEIS Frontend

A244624 Consider the number of lines in the Pratt certificate for the n-th prime (A037202). This sequence shows where 2n first occurs.

Views

Author

Keywords

Comments

Crossrefs

Programs

Mathematica

Formula

A037231 Primes which set a new record for length of Pratt certificate.

Views

Author

Keywords

Links

Crossrefs

Programs

Mathematica

A034697 a(1)=1, a(n)= 1 + Sum a(p), p prime, p | n-1.

Views

Author

Keywords

References

Crossrefs

A177803 The number of lines in the analog of Pratt primality certificate for the n-th semiprime.

Views

Author

Keywords

Examples

Links

Crossrefs

Programs

Maple

Mathematica

Formula

Extensions