A037202 Number of lines in Pratt certificate for n-th prime.

1, 2, 2, 4, 4, 4, 2, 4, 6, 6, 6, 4, 4, 8, 8, 6, 8, 6, 8, 8, 4, 8, 6, 6, 4, 4, 6, 8, 4, 6, 8, 8, 4, 10, 6, 6, 8, 4, 8, 10, 8, 6, 8, 4, 6, 8, 10, 8, 8, 8, 8, 8, 6, 4, 2, 10, 10, 6, 10, 8, 12, 6, 6, 10, 8, 10, 10, 8, 12, 10, 6, 10, 10, 10, 8, 10, 6, 8, 4, 6, 10, 10, 12, 4, 8, 8, 6, 8, 10, 12, 10, 10

Offset: 1

Author

David W. Wilson

Keywords

• nonn
• easy
• nice

Comments

a(k) = 2 for k = 2, 3, 7, 55, 6543, (Fermat Primes, A019434, probably finite),

a(k) = 4 for k = 4, 5, 6, 8, 12, 13, 21, 25, 26, 29, 33, 38, 44, 54, 79, 84, 93, 106, 116, 136, 191, 211, 232, ...,

a(k) = 6 for k = 9, 10, 11, 16, 18, 23, 24, 27, 30, 35, 36, 42, 45, 53, 58, 62, 63, 71, 77, 80, 87, 96, 100, 108, ...,

a(k) = 8 for k = 14, 15, 17, 19, 20, 22, 28, 31, 32, 37, 39, 41, 43, 46, 48, 49, 50, 51, 52, 60, 65, 68, 75, ...,

a(k) = 10 for k = 34, 40, 47, 56, 57, 59, 64, 66, 67, 70, 72, 73, 74, 76, 81, 82, 89, 91, 92, 95, 97, 99, 103, ...,

a(k) = 12 for k = 61, 69, 83, 90, 101, 102, 109, 117, 124, 125, 127, 128, 132, 138, 146, 147, 149, 156, 160, 170, ...,

a(k) = 14 for k = 120, 144, 150, 161, 163, 175, 200, 210, 213, 219, 225, 228, 236, 239, 249, 261, 263, 277, 281, ...,

a(k) = 16 for k = 215, 266, 299, 314, 360, 363, 417, 430, 432, 441, 467, 471, 505, 511, 524, 552, 553, 562, 565, ...,

a(k) = 18 for k = 690, 748, 766, 819, 999, 1027, 1050, 1067, 1105, 1109, 1141, 1154, 1218, 1235, 1259, 1270, ...,

a(k) = 20 for k = 1144, 1393, 1424, 1576, 1719, 1743, 1974, 2133, 2171, 2176, 2205, 2234, 2248, 2259, 2265, 2279, ...,

a(k) = 22 for k = 2584, 3226, 3632, 3659, 3810, 3959, 4127, 4344, 4470, 4588, 4622, 4710, 4747, 4806, 4930, 4936, ...,

a(k) = 24 for k = 5626, 7067, 7324, 7372, 8321, 8670, 8811, 8846, 9237, 9411, 9463, 9605, 9946, 9947, 10518, ...,

a(k) = 26 for k = 13709, 13808, 14659, 16064, 16576, 16596, 18025, 18667, 19223, 19410, 20390, 20731, 20785, ...,

a(k) = 28 for k = 31275, 33607, 39612, 40203, 40648, 42337, 43025, 43312, 44144, 45293, 45335, 45627, 45971, ...,

a(k) = 30 for k = 63461, 63513, 76559, 76858, 81347, 81886, 83430, 86987, 87033, 88871, 94263, 95480, 98307, ...,

a(k) = 32 for k = 145767, 165128, 178829, 186560, 187204, 187472, 204062, 211266, 221035, 230569, 234817, ...,

a(k) = 34 for k = 340332, 356380, 384242, 411259, 458002, 461050, 465782, 467942, 493977, 496416, 514571, ...,

a(k) = 36 for k = 649190, 893950, 982792, 1011067, 1060268, 1071045, 1095110, 1109882, 1142688, 1142952, 1149206, ...,

a(k) = 38 for k = 1703684, 1946813, 2195880, 2198933, 2293897, 2396259, 2480547, 2481840, 2482402, 2493847, ...,

a(k) = 40 for k = 4218462, 4597652, 5001025, 5295255, 5430142, 5438440, 5618213, 5837583, 5860573, 5890121, ...,

etc.

First occurrence of 2k: 2, 4, 9, 14, 34, 61, 120, 215, 690, 1144, 2584, 5626, ..., . - Robert G. Wilson v, Jul 01 2014

References

• E. Bach and Jeffrey Shallit, Algorithmic Number Theory, I, p. 270.

Links

• T. D. Noe, Table of n, a(n) for n = 1..10000
• Eric Weisstein's World of Mathematics, Definition

Crossrefs

Cf. A037231, A034697.

Programs

Mathematica

a[1] = 1; a[n_] := 1 + Plus @@ (a@ PrimePi@ # & /@ First /@ FactorInteger[ Prime@ n - 1]); Array[a, 92]

Formula

a(2)=1, a(n) = 1 + Sum a(p), p prime, p | n-1, where n runs through primes.