求1000以内整数的倒数的循环节长度最长的那个整数是多少?

〇〇

这个是欧拉project中的一题 循环节长度不会大于一个数的字面值，比如1/7的为6，（142857） 合数的倒数的循环节=某个1/x无限因子的循环节，比如1/6=0.166 1/3=0.333

〇〇

若1/n的循环节为x 99999...x的长度.9/x必为整数

〇〇

这个整数就是n

葡萄糖

Project Euler 26 Solution: Reciprocal cycles
https://projecteuler.net/problem=26
https://www.xarg.org/puzzle/project-euler/problem-26/

mathematica

wayne 发表于 2011-4-10 23:18
5# chyanog
可参考3楼zeroieme给的算法,改善 RealDigits 这个瓶颈,参考代码:算得100000以内最长的 是 1/ ...

九年后，再看这个问题

1. Clear["Global`*"];
   
2. (*从2到10^5中，选择与10互质的*)
   
3. aa=Select[Range[2,10^5],GCD[#,10]==1&]
   
4. (*求10的指数*)
   
5. bb={#,MultiplicativeOrder[10,#]}&/@aa
   
6. (*按照第二列从大到小排列*)
   
7. cc=Sort[bb,#1[[2]]>#2[[2]]&]
   

复制代码

部分结果如下：
{99989, 99988}, {99971, 99970}, {99901, 99900}, {99859, 99858}, \
{99833, 99832}, {99829, 99828}, {99817, 99816}, {99793, 99792}, \
{99767, 99766}, {99713, 99712}, {99709, 99708}, {99661, 99660}, \
{99623, 99622}, {99611, 99610}

.·.·.

找以10为原根的素数
1000以内最大的是983
于是没例外了

换句话说，只有比983更大的数字才可能有更大的循环节
首先p/n循环节的长度至多是phi(n)，这就干掉了全部合数
比983大的两个素数循环节都不超过500位，这就已经完成了证明

数论爱好者

素数的倒数的循环节长度用于分解n个1有参考作用,因为在几百个1,几千个1时,软件可能一下不能分解.
1/41,循环节长度为5,那么5个1,即11111一定整除41.
1/4507,循环节长度为751,那么(10^751-1)/9整除4507.

数论爱好者

看了好多例分解(10^n-1)/9,当n为素数时,此式才可能产生素数.若能分解,因子一定具有2*n*k+1的形式.这太难分解,姑且不作研究.
现在只研究素数的倒数的循环节的长度是另一个素数,这从另一个方面找出(10^n-1)/9部分因子.
1/37的循环节长度为3,111=3*37
1/3191的循环节长度为29,(10^29-1)/9=3191*另外的因子
我已经统计1到5000的669个素数,它的循环节长度为素数的共有71个,约等于5000/(ln(5000))^2
哪位大神帮我求一下1到10万的9592个素数,只输出循环节长度为素数的相互对应的资料,估计在800多个.

数论爱好者

快速求素数倒数循环节长度的资料
还是没有搜到仅输出长度是素数的资料
(p-1)/2型
3, 13, 31, 43, 67, 71, 83, 89, 107, 151, 157, 163, 191,

197, 199, 227, 283, 293, 307, 311, 347, 359, 373, 401,

409, 431, 439, 443, 467, 479, 523, 557, 563, 569, 587,

599, 601, 631, 653, 677, 683, 719, 761, 787, 827, 839,

877, 881, 883, 911, 919, 929, 947, 991

p-1型
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

(p-1)/3型
103, 127, 139, 331, 349, 421, 457, 463, 607, 661, 673,

691, 739, 829, 967, 1657, 1669, 1699, 1753, 1993, 2011,

2131, 2287, 2647, 2659, 2749, 2953, 3217, 3229, 3583,

3691, 3697, 3739, 3793, 3823, 3931, 4273, 4297, 4513,

4549, 4657, 4903, 4909, 4993, 5011

(p-1)/4
53, 173, 277, 317, 397, 769, 773, 797, 809, 853, 1009,

1013, 1093, 1493, 1613, 1637, 1693, 1721, 2129, 2213,

2333, 2477, 2521, 2557, 2729, 2797, 2837, 3329, 3373,

3517, 3637, 3733, 3797, 3853, 3877, 4133, 4241, 4253,

4373, 4493, 4729, 4733, 4877, 5081

(p-1)/5
11, 251, 1061, 1451, 1901, 1931, 2381, 3181, 3491, 3851,

4621, 4861, 5261, 6101, 6491, 6581, 6781, 7331, 8101,

9941, 10331, 10771, 11251, 11261, 11411, 12301, 14051,

14221, 14411, 15091, 15131, 16061, 16141, 16301, 16651,

16811, 16901

(p-1)/6
79, 547, 643, 751, 907, 997, 1201, 1213, 1237, 1249,

1483, 1489, 1627, 1723, 1747, 1831, 1879, 1987, 2053,

2551, 2683, 3049, 3253, 3319, 3613, 3919, 4159, 4507,

4519, 4801, 4813, 4831, 4969, 5119, 5443, 5557, 5791,

6079, 6151, 6271, 6373, 6427, 6529

(p-1)/7
211, 617, 1499, 2087, 2857, 6007, 6469, 7127, 7211,

7589, 9661, 10193, 13259, 13553, 14771, 18047, 18257,

19937, 20903, 21379, 23549, 26153, 27259, 27539, 32299,

33181, 33461, 34847, 35491, 35897, 41651, 42407, 42491,

43051, 43793

(p-1)/8
41, 241, 1601, 1609, 2441, 2969, 3041, 3449, 3929, 4001,

4409, 5009, 6089, 6521, 6841, 8161, 8329, 8609, 9001,

9041, 9929, 13001, 13241, 14081, 14929, 16001, 16481,

17489, 17881, 18121, 19001, 20249, 20641, 20921, 21529,

22481, 23801

(p-1)/9
73, 1423, 1459, 2377, 2503, 3457, 7741, 9433, 10891,

10909, 16057, 17299, 17623, 20269, 21313, 22699, 24103,

26263, 28621, 28927, 29629, 30817, 32257, 34273, 34327,

35461, 35731, 36343, 36793, 37549, 37567, 37657, 38737,

39367, 39979

(p-1)/10
281, 521, 1031, 1951, 2281, 2311, 2591, 3671, 5471,

5711, 6791, 7481, 8111, 8681, 8761, 9281, 9551, 10601,

11321, 12401, 13151, 13591, 14831, 14951, 15671, 16111,

16361, 18671, 21191, 21521, 21881, 24281, 24551, 25391,

25801, 25841, 26161

(p-1)/11
353, 3499, 10429, 13619, 15269, 20219, 20593, 23057,

23189, 24091, 25741, 30713, 35509, 38567, 45233, 49171,

57179, 57223, 60149, 63691, 63977, 67783, 77023, 85229,

88463, 90619, 91367, 93941, 96779, 108967, 109913,

110221, 112069

(p-1)/12
37, 613, 733, 1597, 2677, 3037, 4957, 5197, 5641, 7129,

7333, 7573, 8521, 8677, 11317, 14281, 14293, 15289,

15373, 16249, 17053, 17293, 17317, 19441, 20161, 21397,

21613, 21997, 23053, 23197, 24133, 25357, 25717, 26053,

26293, 27277

(p-1)/13
2393, 15497, 18149, 18617, 20021, 25819, 26183, 26339,

29303, 39937, 42953, 48491, 52313, 53327, 57331, 58189,

59021, 65183, 81953, 82499, 87491, 91703, 98047, 102233,

104287, 109097, 111229, 119419, 129793, 131171, 143287,

143833, 162007

数论爱好者

我已经找到一个用maple软件解此类求任意数的倒数循环节长度的方法
图中最后一个数,软件3分钟没有解出来,人脑结合文献资料,一秒钟就知道答案了