Full reptend prime

In number theory, a full reptend prime, full repetend prime, proper prime^[1]^:166 or long prime in base b is a prime number p such that the formula

\frac{b^{p - 1} - 1}{p}

(where p does not divide b) gives a cyclic number. Therefore the digital expansion of $1/p$ in base b repeats the digits of the corresponding cyclic number infinitely, as does that of $a/p$ with rotation of the digits for any a between 1 and p − 1. The cyclic number corresponding to prime p will possess p − 1 digits if and only if p is a full reptend prime. That is, ord_bp = p − 1.

Base 10 may be assumed if no base is specified, in which case the expansion of the number is called a repeating decimal. In base 10, if a full reptend prime ends in the digit 1, then each digit 0, 1, ..., 9 appears in the repetend the same number of times as each other digit.^[1]^:166 (For such primes in base 10, see A073761. In fact, in base n, if a full reptend prime ends in the digit 1, then each digit 0, 1, ..., n−1 appears in the repetend the same number of times as each other digit, but no such prime exists when n = 12, since every full reptend prime in base 12 ends in the digit 5 or 7 in the same base. Generally, no such prime exists when n is congruent to 0 or 1 mod 4)

The values of p less than 1000 for which this formula produces cyclic numbers in decimal are:

7, 17, 19, 23, 29, 47, 59, 61, 97, 109, 113, 131, 149, 167, 179, 181, 193, 223, 229, 233, 257, 263, 269, 313, 337, 367, 379, 383, 389, 419, 433, 461, 487, 491, 499, 503, 509, 541, 571, 577, 593, 619, 647, 659, 701, 709, 727, 743, 811, 821, 823, 857, 863, 887, 937, 941, 953, 971, 977, 983, ... (sequence A001913 in OEIS)

For example, the case b = 10, p = 7 gives the cyclic number 142857; thus 7 is a full reptend prime. Furthermore, 1 divided by 7 written out in base 10 is 0.142857 142857 142857 142857...

Not all values of p will yield a cyclic number using this formula; for example p = 13 gives 076923 076923. These failed cases will always contain a repetition of digits (possibly several) over the course of p − 1 digits.

The known pattern to this sequence comes from algebraic number theory, specifically, this sequence is the set of primes p such that 10 is a primitive root modulo p. Artin's conjecture on primitive roots is that this sequence contains 37.395..% of the primes.

The term "long prime" was used by John Conway and Richard Guy in their Book of Numbers. Confusingly, Sloane's OEIS refers to these primes as "cyclic numbers."

Patterns of occurrence of full reptend primes

Advanced modular arithmetic can show that any prime of the following forms:

40k+1
40k+3
40k+9
40k+13
40k+27
40k+31
40k+37
40k+39

can never be a full reptend prime in base 10. The first primes of these forms, with their periods, are:

40k+1	40k+3	40k+9	40k+13	40k+27	40k+31	40k+37	40k+39
41 period 5	3 period 1	89 period 44	13 period 6	67 period 33	31 period 15	37 period 3	79 period 13
241 period 30	43 period 21	409 period 204	53 period 13	107 period 53	71 period 35	157 period 78	199 period 99
281 period 28	83 period 41	449 period 32	173 period 43	227 period 113	151 period 75	197 period 98	239 period 7
401 period 200	163 period 81	569 period 284	293 period 146	307 period 153	191 period 95	277 period 69	359 period 179
521 period 52	283 period 141	769 period 192	373 period 186	347 period 173	271 period 5	317 period 79	439 period 219
601 period 300	443 period 221	809 period 202	613 period 51	467 period 233	311 period 155	397 period 99	479 period 239

However, studies show that two-thirds of primes of the form 40k+n, where n ∈ {7, 11, 17, 19, 21, 23, 29, 33} are full reptend primes. For some sequences, the preponderance of full reptend primes is much greater. For instance, 285 of the 295 primes of form 120k+23 below 100000 are full reptend primes, with 20903 being the first that is not full reptend.

Base 2 full reptend primes

In base 2, the full reptend primes are: (less than 1000)

3, 5, 11, 13, 19, 29, 37, 53, 59, 61, 67, 83, 101, 107, 131, 139, 149, 163, 173, 179, 181, 197, 211, 227, 269, 293, 317, 347, 349, 373, 379, 389, 419, 421, 443, 461, 467, 491, 509, 523, 541, 547, 557, 563, 587, 613, 619, 653, 659, 661, 677, 701, 709, 757, 773, 787, 797, 821, 827, 829, 853, 859, 877, 883, 907, 941, 947, ... (sequence A001122 in OEIS)

For these primes, 2 is a primitive root modulo p, so 2ⁿ module p can be any natural number between 1 and p − 1.

All of them are of form 8k + 3 or 8k + 5, because if p = 8k + 1 or 8k + 7, then 2 is a quadratic residue modulo p, so p divides $2^{(p - 1)/2} - 1$ , and the period of $1/p$ in base 2 must divide $(p - 1)/2$ and cannot be p − 1, so they are not full reptend primes in base 2.

Further, all safe primes congruent to 3 (mod 8) are full reptend primes in base 2. For example, 3, 11, 59, 83, 107, 179, 227, 347, 467, 563, 587, 1019, 1187, 1283, 1307, 1523, 1619, 1907, etc. (less than 2000)

The following is a list about the periods to the primes congruent to 1 or 7 (mod 8): (less than 1000)

8k + 1	17	41	73	89	97	113	137	193	233	241	257	281	313	337	353	401	409	433	449	457	521	569
period	8	20	9	11	48	28	68	96	29	24	16	70	156	21	88	200	204	72	224	76	260	284
8k + 1	577	593	601	617	641	673	761	769	809	857	881	929	937	953	977	1009	1033	1049	1097	1129	1153	1193
period	144	148	25	154	64	48	380	384	404	428	55	464	117	68	488	504	258	262	274	564	288	298
8k + 7	7	23	31	47	71	79	103	127	151	167	191	199	223	239	263	271	311	359	367	383	431	439
period	3	11	5	23	35	39	51	7	15	83	95	99	37	119	131	135	155	179	183	191	43	73
8k + 7	463	479	487	503	599	607	631	647	719	727	743	751	823	839	863	887	911	919	967	983	991	1031
period	231	239	243	251	299	303	45	323	359	121	371	375	411	419	431	443	91	153	483	491	495	515

The binary period of nth prime are

2, 4, 3, 10, 12, 8, 18, 11, 28, 5, 36, 20, 14, 23, 52, 58, 60, 66, 35, 9, 39, 82, 11, 48, 100, 51, 106, 36, 28, 7, 130, 68, 138, 148, 15, 52, 162, 83, 172, 178, 180, 95, 96, 196, 99, 210, 37, 226, 76, 29, 119, 24, 50, 16, 131, 268, 135, 92, 70, 94, 292, 102, 155, 156, 316, 30, 21, 346, 348, 88, 179, 183, 372, 378, 191, 388, 44, ... (this sequence starts at n = 2, or the prime = 3) (sequence A014664 in OEIS)

The binary period level of nth prime are

1, 1, 2, 1, 1, 2, 1, 2, 1, 6, 1, 2, 3, 2, 1, 1, 1, 1, 2, 8, 2, 1, 8, 2, 1, 2, 1, 3, 4, 18, 1, 2, 1, 1, 10, 3, 1, 2, 1, 1, 1, 2, 2, 1, 2, 1, 6, 1, 3, 8, 2, 10, 5, 16, 2, 1, 2, 3, 4, 3, 1, 3, 2, 2, 1, 11, 16, 1, 1, 4, 2, 2, 1, 1, 2, 1, 9, 2, 2, 1, 1, 10, 6, 6, 1, 2, 6, 1, 2, 1, 2, 2, 1, 3, 2, 1, 2, 1, 1, ... (sequence A001917 in OEIS)

However, studies show that three-fourths of primes of the form 8k+n, where n ∈ {3, 5} are full reptend primes in base 2 (For example, there are 87 primes below 1000 congruent to 3 or 5 (mod 8), and 67 of them are full-reptend in base 2, it is total 77%). For some sequences, the preponderance of full reptend primes is much greater. For instance, 1078 of the 1206 primes of form 24k+5 below 100000 are full reptend primes in base 2, with 1013 being the first that is not full reptend in base 2.

Full reptend primes in various bases

Artin also conjectured:

There are infinitely many full-reptend primes in all bases except squares.
Full-reptend primes in all bases except perfect powers and numbers whose squarefree part are congruent to 1 to mod 4 comprise 37.395...% of all primes. (See A085397)

Base	Full reptend primes	OEIS sequence
−30	7, 41, 61, 83, 89, 107, 109, 127, 139, 173, 193, 197, 211, 227, 239, 281, 293, 311, 317, 331, 347, 349, 359, ...	A105902
−29	2, 17, 23, 41, 59, 71, 73, 83, 89, 97, 101, 103, 107, 113, 137, 139, 167, 179, 199, 223, 227, 229, 239, 269, ...	A105901
−28	3, 5, 13, 17, 19, 31, 41, 47, 59, 73, 83, 89, 101, 103, 131, 139, 167, 173, 181, 227, 229, 251, 257, 269, 283, ...	A105900
−27	2, 5, 11, 17, 23, 29, 47, 53, 59, 71, 83, 89, 101, 107, 113, 131, 137, 149, 167, 173, 179, 191, 197, 227, 233, ...	A105875
−26	11, 23, 29, 41, 53, 59, 61, 67, 73, 79, 83, 89, 97, 101, 103, 127, 137, 157, 163, 173, 191, 193, 199, 227, 263, ...	A105898
−25	2, 3, 7, 11, 19, 23, 43, 47, 59, 79, 83, 103, 107, 131, 139, 151, 167, 179, 223, 227, 239, 263, 283, 307, 311, ...	A105897
−24	13, 17, 19, 37, 41, 43, 47, 71, 89, 109, 113, 137, 139, 157, 163, 167, 181, 191, 211, 229, 233, 257, 263, 277, ...	A105896
−23	2, 5, 7, 17, 19, 43, 67, 83, 89, 97, 107, 113, 137, 149, 181, 191, 199, 227, 229, 251, 263, 281, 283, 293, 337, ...	A105895
−22	3, 5, 17, 37, 41, 53, 59, 151, 167, 179, 193, 233, 251, 263, 269, 271, 281, 317, 337, 359, 379, 389, 397, 409, ...	A105894
−21	2, 29, 47, 53, 59, 67, 83, 97, 113, 127, 131, 137, 149, 151, 157, 167, 181, 197, 227, 233, 251, 281, 311, 313, ...	A105893
−20	11, 13, 17, 31, 37, 53, 59, 73, 79, 113, 131, 137, 139, 157, 173, 179, 191, 199, 211, 233, 239, 257, 271, 277, ...	A105892
−19	2, 3, 13, 29, 31, 37, 41, 53, 59, 67, 71, 79, 89, 103, 107, 113, 167, 173, 179, 193, 223, 227, 257, 269, 281, ...	A105891
−18	5, 7, 23, 29, 31, 37, 47, 53, 61, 71, 101, 103, 109, 127, 149, 151, 157, 167, 173, 181, 191, 197, 223, 239, ...	A105890
−17	2, 5, 19, 37, 41, 43, 47, 59, 61, 67, 83, 97, 103, 113, 127, 151, 173, 179, 191, 193, 197, 233, 239, 251, 263, ...	A105889
−16	3, 7, 11, 19, 23, 47, 59, 67, 71, 79, 83, 103, 107, 131, 139, 163, 167, 179, 191, 199, 211, 227, 239, 263, 271, ...	A105876
−15	2, 11, 13, 29, 37, 41, 43, 59, 71, 73, 89, 97, 101, 103, 127, 131, 149, 157, 163, 179, 191, 193, 239, 251, 269, ...	A105887
−14	11, 17, 29, 31, 43, 47, 53, 73, 89, 97, 107, 109, 149, 163, 167, 179, 199, 241, 257, 271, 277, 311, 313, 317, ...	A105886
−13	2, 3, 5, 23, 37, 41, 43, 73, 79, 89, 97, 107, 109, 127, 131, 137, 139, 149, 179, 191, 197, 199, 241, 251, 263, ...	A105885
−12	5, 17, 23, 41, 47, 53, 59, 71, 83, 101, 107, 113, 131, 137, 149, 167, 173, 179, 191, 197, 227, 239, 251, 257, ...	A105884
−11	2, 7, 13, 17, 29, 41, 73, 79, 83, 101, 107, 109, 127, 131, 139, 149, 151, 167, 173, 197, 227, 233, 239, 263, ...	A105883
−10	3, 17, 29, 31, 43, 61, 67, 71, 83, 97, 107, 109, 113, 149, 151, 163, 181, 191, 193, 199, 227, 229, 233, 257, ...	A007348
−9	2, 7, 11, 19, 23, 31, 43, 47, 59, 71, 79, 83, 107, 127, 131, 139, 163, 167, 179, 191, 199, 211, 223, 227, 239, ...	A105881
−8	5, 23, 29, 47, 53, 71, 101, 149, 167, 173, 191, 197, 239, 263, 269, 293, 311, 317, 359, 383, 389, 461, 479, ...	A105880
−7	2, 3, 5, 13, 17, 31, 41, 47, 59, 61, 83, 89, 97, 101, 103, 131, 139, 167, 173, 199, 227, 229, 241, 251, 257, ...	A105879
−6	13, 17, 19, 23, 41, 47, 61, 67, 71, 89, 109, 113, 137, 157, 167, 211, 229, 233, 257, 263, 277, 283, 331, 359, ...	A105878
−5	2, 11, 17, 19, 37, 53, 59, 73, 79, 97, 113, 131, 137, 139, 151, 157, 173, 179, 193, 197, 233, 239, 257, 277, ...	A105877
−4	3, 7, 11, 19, 23, 47, 59, 67, 71, 79, 83, 103, 107, 131, 139, 163, 167, 179, 191, 199, 211, 227, 239, 263, 271, ...	A105876
−3	2, 5, 11, 17, 23, 29, 47, 53, 59, 71, 83, 89, 101, 107, 113, 131, 137, 149, 167, 173, 179, 191, 197, 227, 233, ...	A105875
−2	5, 7, 13, 23, 29, 37, 47, 53, 61, 71, 79, 101, 103, 149, 167, 173, 181, 191, 197, 199, 239, 263, 269, 271, 293, ...	A105874
2	3, 5, 11, 13, 19, 29, 37, 53, 59, 61, 67, 83, 101, 107, 131, 139, 149, 163, 173, 179, 181, 197, 211, 227, 269, ...	A001122
3	2, 5, 7, 17, 19, 29, 31, 43, 53, 79, 89, 101, 113, 127, 137, 139, 149, 163, 173, 197, 199, 211, 223, 233, 257, ...	A019334
4	(none)
5	2, 3, 7, 17, 23, 37, 43, 47, 53, 73, 83, 97, 103, 107, 113, 137, 157, 167, 173, 193, 197, 223, 227, 233, 257, ...	A019335
6	11, 13, 17, 41, 59, 61, 79, 83, 89, 103, 107, 109, 113, 127, 131, 137, 151, 157, 179, 199, 223, 227, 229, 233, ...	A019336
7	2, 5, 11, 13, 17, 23, 41, 61, 67, 71, 79, 89, 97, 101, 107, 127, 151, 163, 173, 179, 211, 229, 239, 241, 257, ...	A019337
8	3, 5, 11, 29, 53, 59, 83, 101, 107, 131, 149, 173, 179, 197, 227, 269, 293, 317, 347, 389, 419, 443, 461, 467, ...	A019338
9	2 (no others)
10	7, 17, 19, 23, 29, 47, 59, 61, 97, 109, 113, 131, 149, 167, 179, 181, 193, 223, 229, 233, 257, 263, 269, 313, ...	A001913
11	2, 3, 13, 17, 23, 29, 31, 41, 47, 59, 67, 71, 73, 101, 103, 109, 149, 163, 173, 179, 197, 223, 233, 251, 277, ...	A019339
12	5, 7, 17, 31, 41, 43, 53, 67, 101, 103, 113, 127, 137, 139, 149, 151, 163, 173, 197, 223, 257, 269, 281, 283, ...	A019340
13	2, 5, 11, 19, 31, 37, 41, 47, 59, 67, 71, 73, 83, 89, 97, 109, 137, 149, 151, 167, 197, 227, 239, 241, 281, 293, ...	A019341
14	3, 17, 19, 23, 29, 53, 59, 73, 83, 89, 97, 109, 127, 131, 149, 151, 227, 239, 241, 251, 257, 263, 277, 283, 307, ...	A019342
15	2, 13, 19, 23, 29, 37, 41, 47, 73, 83, 89, 97, 101, 107, 139, 149, 151, 157, 167, 193, 199, 227, 263, 269, 271, ...	A019343
16	(none)
17	2, 3, 5, 7, 11, 23, 31, 37, 41, 61, 97, 107, 113, 131, 139, 167, 173, 193, 197, 211, 227, 233, 269, 277, 283, ...	A019344
18	5, 11, 29, 37, 43, 53, 59, 61, 67, 83, 101, 107, 109, 139, 149, 157, 163, 173, 179, 181, 197, 227, 251, 269, ...	A019345
19	2, 7, 11, 13, 23, 29, 37, 41, 43, 47, 53, 83, 89, 113, 139, 163, 173, 191, 193, 239, 251, 257, 263, 269, 281, ...	A019346
20	3, 13, 17, 23, 37, 43, 47, 53, 67, 73, 83, 103, 107, 113, 137, 157, 163, 167, 173, 223, 227, 233, 257, 263, 277, ...	A019347
21	2, 19, 23, 29, 31, 53, 71, 97, 103, 107, 113, 137, 139, 149, 157, 179, 181, 191, 197, 223, 233, 239, 263, 271, ...	A019348
22	5, 17, 19, 31, 37, 41, 47, 53, 71, 83, 107, 131, 139, 191, 193, 199, 211, 223, 227, 233, 269, 281, 283, 307, ...	A019349
23	2, 3, 5, 17, 47, 59, 89, 97, 113, 127, 131, 137, 149, 167, 179, 181, 223, 229, 281, 293, 307, 311, 337, 347, ...	A019350
24	7, 11, 13, 17, 31, 37, 41, 59, 83, 89, 107, 109, 113, 137, 157, 179, 181, 223, 227, 229, 233, 251, 257, 277, ...	A019351
25	2 (no others)
26	3, 7, 29, 41, 43, 47, 53, 61, 73, 89, 97, 101, 107, 131, 137, 139, 157, 167, 173, 179, 193, 239, 251, 269, 271, ...	A019352
27	2, 5, 17, 29, 53, 89, 101, 113, 137, 149, 173, 197, 233, 257, 269, 281, 293, 317, 353, 389, 401, 449, 461, 509, ...	A019353
28	5, 11, 13, 17, 23, 41, 43, 67, 71, 73, 79, 89, 101, 107, 173, 179, 181, 191, 229, 257, 263, 269, 293, 313, 331, ...	A019354
29	2, 3, 11, 17, 19, 41, 43, 47, 73, 79, 89, 97, 101, 113, 127, 131, 137, 163, 191, 211, 229, 251, 263, 269, 293, ...	A019355
30	11, 23, 41, 43, 47, 59, 61, 79, 89, 109, 131, 151, 167, 173, 179, 193, 197, 199, 251, 263, 281, 293, 307, 317, ...	A019356

The smallest full-reptend primes in base n are:

2, 3, 2, 0, 2, 11, 2, 3, 2, 7, 2, 5, 2, 3, 2, 0, 2, 5, 2, 3, 2, 5, 2, 7, 2, 3, 2, 5, 2, 11, 2, 3, 2, 19, 2, 0, 2, 3, 2, 7, 2, 5, 2, 3, 2, 11, 2, 5, 2, 3, 2, 5, 2, 7, 2, 3, 2, 5, 2, 19, 2, 3, 2, 0, 2, 7, 2, 3, 2, 19, 2, 5, ... (sequence A056619 in OEIS)

Applications to cryptography

Binary full reptend prime sequences (also called maximum-length decimal sequences) have found cryptographic and error-correction coding applications.^[2] In these applications, repeating decimals to base 2 are generally used which gives rise to binary sequences. The maximum length binary sequence for $1/p$ (when 2 is a primitive root of p) is given by:^[3]

a(i) = 2^{i}~\bmod p ~\bmod 2

These sequences of period p − 1 have an autocorrelation function that has a negative peak of −1 for shift of $(p - 1)/2$ . The randomness of these sequences has been examined by diehard tests.^[4]

References

1 2 Dickson, Leonard E., 1952, History of the Theory of Numbers, Volume 1, Chelsea Public. Co.
↑ Kak, Subhash, Chatterjee, A. "On decimal sequences." IEEE Transactions on Information Theory, vol. IT-27, pp. 647-652, September 1981.
↑ Kak, Subhash, "Encryption and error-correction using d-sequences." IEEE Trans. On Computers, vol. C-34, pp. 803-809, 1985.
↑ Bellamy, J. "Randomness of D sequences via diehard testing." 2013. arXiv:1312.3618

Weisstein, Eric W., "Artin's Constant", MathWorld.
Weisstein, Eric W., "Full Reptend Prime", MathWorld.
Conway, J. H. and Guy, R. K. The Book of Numbers. New York: Springer-Verlag, 1996.
Francis, Richard L.; "Mathematical Haystacks: Another Look at Repunit Numbers"; in The College Mathematics Journal, Vol. 19, No. 3. (May, 1988), pp. 240–246.

Prime number classes

By formula	Fermat (2^2ⁿ + 1) Mersenne (2^p − 1) Double Mersenne (2^{2^p−1} − 1) Wagstaff (2^p + 1)/3 Proth (k·2ⁿ + 1) Factorial (n! ± 1) Primorial (p_n# ± 1) Euclid (p_n# + 1) Pythagorean (4n + 1) Pierpont (2^u·3^v + 1) Quartan (x⁴ + y⁴) Solinas (2^a ± 2^b ± 1) Cullen (n·2ⁿ + 1) Woodall (n·2ⁿ − 1) Cuban (x³ − y³)/(x − y) Carol (2ⁿ − 1)² − 2 Kynea (2ⁿ + 1)² − 2 Leyland (x^y + y^x) Thabit (3·2ⁿ − 1) Mills (floor(A^3ⁿ))

By integer sequence	Fibonacci Lucas Pell Newman–Shanks–Williams Perrin Partitions Bell Motzkin

By property	Wieferich (pair) Wall–Sun–Sun Wolstenholme Wilson Lucky Fortunate Ramanujan Pillai Regular Strong Stern Supersingular (elliptic curve) Supersingular (moonshine theory) Good Super Higgs Highly cototient

Base-dependent	Happy Dihedral Palindromic Emirp Repunit (10ⁿ − 1)/9 Permutable Circular Truncatable Strobogrammatic Minimal Weakly Full reptend Unique Primeval Self Smarandache–Wellin

Patterns	Twin (p, p + 2) Bi-twin chain (n − 1, n + 1, 2n − 1, 2n + 1, …) Triplet (p, p + 2 or p + 4, p + 6) Quadruplet (p, p + 2, p + 6, p + 8) k−Tuple Cousin (p, p + 4) Sexy (p, p + 6) Chen Sophie Germain (p, 2p + 1) Cunningham chain (p, 2p ± 1, …) Safe (p, (p − 1)/2) Arithmetic progression (p + a·n, n = 0, 1, …) Balanced (consecutive p − n, p, p + n)

By size	Titanic (1,000+ digits) Gigantic (10,000+) Mega (1,000,000+) Largest known

Complex numbers	Eisenstein prime Gaussian prime

Composite numbers	Pseudoprime Almost prime Semiprime Interprime

Related topics	Probable prime Industrial-grade prime Illegal prime Formula for primes Prime gap

First 100 primes	2 3 5 7 11 13 17 19 23 29 31 37 41 43 47 53 59 61 67 71 73 79 83 89 97 101 103 107 109 113 127 131 137 139 149 151 157 163 167 173 179 181 191 193 197 199 211 223 227 229 233 239 241 251 257 263 269 271 277 281 283 293 307 311 313 317 331 337 347 349 353 359 367 373 379 383 389 397 401 409 419 421 431 433 439 443 449 457 461 463 467 479 487 491 499 503 509 521 523 541

List of prime numbers

This article is issued from Wikipedia - version of the Monday, April 25, 2016. The text is available under the Creative Commons Attribution/Share Alike but additional terms may apply for the media files.