关于自守数

无心人

wayne你抢我买卖 似乎n次幂的自守数，和n的素因子分解有关系啊

无心人

最后一个101的， 竟然有909个 Prelude> stepSP 101 6 [(6,0),(6,1),(6,1249),(6,2943),(6,4193),(6,5807),(6,7057),(6,8751),(6,9999),(6,1 0001),(6,10624),(6,11249),(6,12943),(6,13568),(6,14193),(6,15807),(6,17057),(6,1 8751),(6,19999),(6,20001),(6,21249),(6,22943),(6,24193),(6,25807),(6,26432),(6,2 7057),(6,28751),(6,29376),(6,29999),(6,30001),(6,31249),(6,32943),(6,34193),(6,3 5807),(6,37057),(6,38751),(6,39999),(6,40001),(6,41249),(6,42943),(6,44193),(6,4 5807),(6,47057),(6,48751),(6,49999),(6,50001),(6,50624),(6,51249),(6,52943),(6,5 3568),(6,54193),(6,55807),(6,57057),(6,58751),(6,59999),(6,60001),(6,61249),(6,6 2943),(6,64193),(6,65807),(6,66432),(6,67057),(6,68751),(6,69376),(6,69999),(6,7 0001),(6,71249),(6,72943),(6,74193),(6,75807),(6,77057),(6,78751),(6,79999),(6,8 0001),(6,81249),(6,82943),(6,84193),(6,85807),(6,87057),(6,88751),(6,89999),(6,9 0001),(6,90624),(6,91249),(6,92943),(6,93568),(6,94193),(6,95807),(6,97057),(6,9 8751),(6,99999),(6,100001),(6,101249),(6,102943),(6,104193),(6,105807),(6,106432 ),(6,107057),(6,108751),(6,109375),(6,109376),(6,109999),(6,110001),(6,111249),( 6,112943),(6,114193),(6,115807),(6,117057),(6,118751),(6,119999),(6,120001),(6,1 21249),(6,122943),(6,124193),(6,125807),(6,127057),(6,128751),(6,129999),(6,1300 01),(6,130624),(6,131249),(6,132943),(6,133568),(6,134193),(6,135807),(6,137057) ,(6,138751),(6,139999),(6,140001),(6,140625),(6,141249),(6,142943),(6,144193),(6 ,145807),(6,146432),(6,147057),(6,148751),(6,149376),(6,149999),(6,150001),(6,15 1249),(6,152943),(6,154193),(6,155807),(6,157057),(6,158751),(6,159999),(6,16000 1),(6,161249),(6,162943),(6,164193),(6,165807),(6,167057),(6,168751),(6,169999), (6,170001),(6,170624),(6,171249),(6,172943),(6,173568),(6,174193),(6,175807),(6, 177057),(6,178751),(6,179999),(6,180001),(6,181249),(6,182943),(6,184193),(6,185 807),(6,186432),(6,187057),(6,188751),(6,189376),(6,189999),(6,190001),(6,191249 ),(6,192943),(6,194193),(6,195807),(6,197057),(6,198751),(6,199999),(6,200001),( 6,201249),(6,202943),(6,204193),(6,205807),(6,207057),(6,208751),(6,209999),(6,2 10001),(6,210624),(6,211249),(6,212943),(6,213568),(6,214193),(6,215807),(6,2170 57),(6,218751),(6,219999),(6,220001),(6,221249),(6,222943),(6,224193),(6,225807) ,(6,226432),(6,227057),(6,228751),(6,229376),(6,229999),(6,230001),(6,231249),(6 ,232943),(6,234193),(6,235807),(6,237057),(6,238751),(6,239999),(6,240001),(6,24 1249),(6,242943),(6,244193),(6,245807),(6,247057),(6,248751),(6,249999),(6,25000 1),(6,250624),(6,251249),(6,252943),(6,253568),(6,254193),(6,255807),(6,257057), (6,258751),(6,259999),(6,260001),(6,261249),(6,262943),(6,264193),(6,265807),(6, 266432),(6,267057),(6,268751),(6,269376),(6,269999),(6,270001),(6,271249),(6,272 943),(6,274193),(6,275807),(6,277057),(6,278751),(6,279999),(6,280001),(6,281249 ),(6,282943),(6,284193),(6,285807),(6,287057),(6,288751),(6,289999),(6,290001),( 6,290624),(6,291249),(6,292943),(6,293568),(6,294193),(6,295807),(6,297057),(6,2 98751),(6,299999),(6,300001),(6,301249),(6,302943),(6,304193),(6,305807),(6,3064 32),(6,307057),(6,308751),(6,309376),(6,309999),(6,310001),(6,311249),(6,312943) ,(6,314193),(6,315807),(6,317057),(6,318751),(6,319999),(6,320001),(6,321249),(6 ,322943),(6,324193),(6,325807),(6,327057),(6,328751),(6,329999),(6,330001),(6,33 0624),(6,331249),(6,332943),(6,333568),(6,334193),(6,335807),(6,337057),(6,33875 1),(6,339999),(6,340001),(6,341249),(6,342943),(6,344193),(6,345807),(6,346432), (6,347057),(6,348751),(6,349376),(6,349999),(6,350001),(6,351249),(6,352943),(6, 354193),(6,355807),(6,357057),(6,358751),(6,359375),(6,359999),(6,360001),(6,361 249),(6,362943),(6,364193),(6,365807),(6,367057),(6,368751),(6,369999),(6,370001 ),(6,370624),(6,371249),(6,372943),(6,373568),(6,374193),(6,375807),(6,377057),( 6,378751),(6,379999),(6,380001),(6,381249),(6,382943),(6,384193),(6,385807),(6,3 86432),(6,387057),(6,388751),(6,389376),(6,389999),(6,390001),(6,390625),(6,3912 49),(6,392943),(6,394193),(6,395807),(6,397057),(6,398751),(6,399999),(6,400001) ,(6,401249),(6,402943),(6,404193),(6,405807),(6,407057),(6,408751),(6,409999),(6 ,410001),(6,410624),(6,411249),(6,412943),(6,413568),(6,414193),(6,415807),(6,41 7057),(6,418751),(6,419999),(6,420001),(6,421249),(6,422943),(6,424193),(6,42580 7),(6,426432),(6,427057),(6,428751),(6,429376),(6,429999),(6,430001),(6,431249), (6,432943),(6,434193),(6,435807),(6,437057),(6,438751),(6,439999),(6,440001),(6, 441249),(6,442943),(6,444193),(6,445807),(6,447057),(6,448751),(6,449999),(6,450 001),(6,450624),(6,451249),(6,452943),(6,453568),(6,454193),(6,455807),(6,457057 ),(6,458751),(6,459999),(6,460001),(6,461249),(6,462943),(6,464193),(6,465807),( 6,466432),(6,467057),(6,468751),(6,469376),(6,469999),(6,470001),(6,471249),(6,4 72943),(6,474193),(6,475807),(6,477057),(6,478751),(6,479999),(6,480001),(6,4812 49),(6,482943),(6,484193),(6,485807),(6,487057),(6,488751),(6,489999),(6,490001) ,(6,490624),(6,491249),(6,492943),(6,493568),(6,494193),(6,495807),(6,497057),(6 ,498751),(6,499999),(6,500001),(6,501249),(6,502943),(6,504193),(6,505807),(6,50 6432),(6,507057),(6,508751),(6,509376),(6,509999),(6,510001),(6,511249),(6,51294 3),(6,514193),(6,515807),(6,517057),(6,518751),(6,519999),(6,520001),(6,521249), (6,522943),(6,524193),(6,525807),(6,527057),(6,528751),(6,529999),(6,530001),(6, 530624),(6,531249),(6,532943),(6,533568),(6,534193),(6,535807),(6,537057),(6,538 751),(6,539999),(6,540001),(6,541249),(6,542943),(6,544193),(6,545807),(6,546432 ),(6,547057),(6,548751),(6,549376),(6,549999),(6,550001),(6,551249),(6,552943),( 6,554193),(6,555807),(6,557057),(6,558751),(6,559999),(6,560001),(6,561249),(6,5 62943),(6,564193),(6,565807),(6,567057),(6,568751),(6,569999),(6,570001),(6,5706 24),(6,571249),(6,572943),(6,573568),(6,574193),(6,575807),(6,577057),(6,578751) ,(6,579999),(6,580001),(6,581249),(6,582943),(6,584193),(6,585807),(6,586432),(6 ,587057),(6,588751),(6,589376),(6,589999),(6,590001),(6,591249),(6,592943),(6,59 4193),(6,595807),(6,597057),(6,598751),(6,599999),(6,600001),(6,601249),(6,60294 3),(6,604193),(6,605807),(6,607057),(6,608751),(6,609375),(6,609999),(6,610001), (6,610624),(6,611249),(6,612943),(6,613568),(6,614193),(6,615807),(6,617057),(6, 618751),(6,619999),(6,620001),(6,621249),(6,622943),(6,624193),(6,625807),(6,626 432),(6,627057),(6,628751),(6,629376),(6,629999),(6,630001),(6,631249),(6,632943 ),(6,634193),(6,635807),(6,637057),(6,638751),(6,639999),(6,640001),(6,640625),( 6,641249),(6,642943),(6,644193),(6,645807),(6,647057),(6,648751),(6,649999),(6,6 50001),(6,650624),(6,651249),(6,652943),(6,653568),(6,654193),(6,655807),(6,6570 57),(6,658751),(6,659999),(6,660001),(6,661249),(6,662943),(6,664193),(6,665807) ,(6,666432),(6,667057),(6,668751),(6,669376),(6,669999),(6,670001),(6,671249),(6 ,672943),(6,674193),(6,675807),(6,677057),(6,678751),(6,679999),(6,680001),(6,68 1249),(6,682943),(6,684193),(6,685807),(6,687057),(6,688751),(6,689999),(6,69000 1),(6,690624),(6,691249),(6,692943),(6,693568),(6,694193),(6,695807),(6,697057), (6,698751),(6,699999),(6,700001),(6,701249),(6,702943),(6,704193),(6,705807),(6, 706432),(6,707057),(6,708751),(6,709376),(6,709999),(6,710001),(6,711249),(6,712 943),(6,714193),(6,715807),(6,717057),(6,718751),(6,719999),(6,720001),(6,721249 ),(6,722943),(6,724193),(6,725807),(6,727057),(6,728751),(6,729999),(6,730001),( 6,730624),(6,731249),(6,732943),(6,733568),(6,734193),(6,735807),(6,737057),(6,7 38751),(6,739999),(6,740001),(6,741249),(6,742943),(6,744193),(6,745807),(6,7464 32),(6,747057),(6,748751),(6,749376),(6,749999),(6,750001),(6,751249),(6,752943) ,(6,754193),(6,755807),(6,757057),(6,758751),(6,759999),(6,760001),(6,761249),(6 ,762943),(6,764193),(6,765807),(6,767057),(6,768751),(6,769999),(6,770001),(6,77 0624),(6,771249),(6,772943),(6,773568),(6,774193),(6,775807),(6,777057),(6,77875 1),(6,779999),(6,780001),(6,781249),(6,782943),(6,784193),(6,785807),(6,786432), (6,787057),(6,788751),(6,789376),(6,789999),(6,790001),(6,791249),(6,792943),(6, 794193),(6,795807),(6,797057),(6,798751),(6,799999),(6,800001),(6,801249),(6,802 943),(6,804193),(6,805807),(6,807057),(6,808751),(6,809999),(6,810001),(6,810624 ),(6,811249),(6,812943),(6,813568),(6,814193),(6,815807),(6,817057),(6,818751),( 6,819999),(6,820001),(6,821249),(6,822943),(6,824193),(6,825807),(6,826432),(6,8 27057),(6,828751),(6,829376),(6,829999),(6,830001),(6,831249),(6,832943),(6,8341 93),(6,835807),(6,837057),(6,838751),(6,839999),(6,840001),(6,841249),(6,842943) ,(6,844193),(6,845807),(6,847057),(6,848751),(6,849999),(6,850001),(6,850624),(6 ,851249),(6,852943),(6,853568),(6,854193),(6,855807),(6,857057),(6,858751),(6,85 9375),(6,859999),(6,860001),(6,861249),(6,862943),(6,864193),(6,865807),(6,86643 2),(6,867057),(6,868751),(6,869376),(6,869999),(6,870001),(6,871249),(6,872943), (6,874193),(6,875807),(6,877057),(6,878751),(6,879999),(6,880001),(6,881249),(6, 882943),(6,884193),(6,885807),(6,887057),(6,888751),(6,889999),(6,890001),(6,890 624),(6,890625),(6,891249),(6,892943),(6,893568),(6,894193),(6,895807),(6,897057 ),(6,898751),(6,899999),(6,900001),(6,901249),(6,902943),(6,904193),(6,905807),( 6,906432),(6,907057),(6,908751),(6,909376),(6,909999),(6,910001),(6,911249),(6,9 12943),(6,914193),(6,915807),(6,917057),(6,918751),(6,919999),(6,920001),(6,9212 49),(6,922943),(6,924193),(6,925807),(6,927057),(6,928751),(6,929999),(6,930001) ,(6,930624),(6,931249),(6,932943),(6,933568),(6,934193),(6,935807),(6,937057),(6 ,938751),(6,939999),(6,940001),(6,941249),(6,942943),(6,944193),(6,945807),(6,94 6432),(6,947057),(6,948751),(6,949376),(6,949999),(6,950001),(6,951249),(6,95294 3),(6,954193),(6,955807),(6,957057),(6,958751),(6,959999),(6,960001),(6,961249), (6,962943),(6,964193),(6,965807),(6,967057),(6,968751),(6,969999),(6,970001),(6, 970624),(6,971249),(6,972943),(6,973568),(6,974193),(6,975807),(6,977057),(6,978 751),(6,979999),(6,980001),(6,981249),(6,982943),(6,984193),(6,985807),(6,986432 ),(6,987057),(6,988751),(6,989376),(6,989999),(6,990001),(6,991249),(6,992943),( 6,994193),(6,995807),(6,997057),(6,998751),(6,999999)]

mathe

$x^{k+1}-=x(mod 10^n)$ 等价于$x(x^k-1) -= 0 (mod 10^n)$ 其中$(x,x^k-1)=1$, 我们知道$x-=0(mod 2^n)$和$x-=0(mod 5^n)$都是唯一解 而$x^k-1 -=0(mod 5^n)$的解中，显然x不是5的倍数。由于$\phi(5^n)=4*5^{n-1}$,所以解的数目只同k的因子2和因子5的数目相关,由于同5互素模$5^n$数构成一个有原根的乘法群,所以其模$5^n$解的数目是$gcd(k,4*5^{n-1})$.由此得到$x(x^k-1)-=0(mod 5^n)$解的数目是$1+gcd(k,4*5^{n-1})$ 而对于$n>=3,x^k-1 -=0(mod 2^n)$的解的数目在k是奇数时为1，而在k为偶数时为$2*gcd(k,2^{n-2})$ 所以$x(x^k-1)-=0(mod 2^n)$在k奇数时解的数目为2，但是k为偶数时数目为$1+2*gcd(k,2^{n-2})$ 而最终解的数目为模$5^n$的数目和模$2^n$数目的乘积。 所以k为奇数时数目为$2(1+gcd(k,4*5^{n-1}))$,而k为偶数时是$(1+gcd(k,4*5^{n-1}))(1+2*gcd(k,2^{n-2}))$ 比如22#对应k=100,所以数目为$(1+gcd(100,4*5^5))(1+2*gcd(100,2^4))=101*9=909$

mathe

如果用算法求所有解，一种比较快速的方法就是分别求出模$2^n$和$5^n$的所有解，然后用中国剩余定理构造所有解。而其中关于两个模为0的解不需要计算。而对于余下的解，我们可以通过随机法得到。 比如对于模$5^n$,设$gcd(k,4*5^{n-1})=h$,我们随机选择一个不含因子5的数，计算它关于模$5^n$的次数，如果这个次数不是h的倍数，放弃，另外产生一个数，知道产生达到要求的数（由于原根比例很高，通常很快可以找到满足要求的数）。然后如果这个数的次数大于h,那么可以计算它的若干倍使得新的数次数为h. 有了次数为h的一个数，那么它的任意次方就构成了所有解。

gxqcn

真精彩！

wayne

wayne你抢我买卖 似乎n次幂的自守数，和n的素因子分解有关系啊 无心人 发表于 2011-6-10 16:32

，好吧，让我来贴一个给力点的 ， 我喜欢2，就贴22次幂的吧：

1. 1
2. 25
3. 76
4. 376
5. 625
6. 9376
7. 90625
8. 109376
9. 890625
10. 2890625
11. 7109376
12. 12890625
13. 87109376
14. 212890625
15. 787109376
16. 1787109376
17. 8212890625
18. 18212890625
19. 81787109376
20. 918212890625
21. 9918212890625
22. 40081787109376
23. 59918212890625
24. 259918212890625
25. 740081787109376
26. 3740081787109376
27. 6259918212890625
28. 43740081787109376
29. 56259918212890625
30. 256259918212890625
31. 743740081787109376
32. 2256259918212890625
33. 7743740081787109376
34. 92256259918212890625
35. 392256259918212890625
36. 607743740081787109376
37. 2607743740081787109376
38. 7392256259918212890625
39. 22607743740081787109376
40. 77392256259918212890625
41. 977392256259918212890625
42. 9977392256259918212890625
43. 19977392256259918212890625
44. 80022607743740081787109376
45. 380022607743740081787109376
46. 619977392256259918212890625
47. 3380022607743740081787109376
48. 6619977392256259918212890625
49. 93380022607743740081787109376
50. 106619977392256259918212890625
51. 893380022607743740081787109376
52. 4106619977392256259918212890625
53. 5893380022607743740081787109376
54. 95893380022607743740081787109376
55. 995893380022607743740081787109376
56. 9004106619977392256259918212890625
57. 90995893380022607743740081787109376
58. 109004106619977392256259918212890625
59. 890995893380022607743740081787109376
60. 3890995893380022607743740081787109376
61. 6109004106619977392256259918212890625
62. 96109004106619977392256259918212890625
63. 103890995893380022607743740081787109376
64. 896109004106619977392256259918212890625
65. 9103890995893380022607743740081787109376
66. 30896109004106619977392256259918212890625
67. 69103890995893380022607743740081787109376
68. 230896109004106619977392256259918212890625
69. 769103890995893380022607743740081787109376
70. 3230896109004106619977392256259918212890625
71. 6769103890995893380022607743740081787109376
72. 23230896109004106619977392256259918212890625
73. 76769103890995893380022607743740081787109376
74. 423230896109004106619977392256259918212890625
75. 576769103890995893380022607743740081787109376
76. 3423230896109004106619977392256259918212890625
77. 6576769103890995893380022607743740081787109376
78. 23423230896109004106619977392256259918212890625
79. 76576769103890995893380022607743740081787109376
80. 423423230896109004106619977392256259918212890625
81. 576576769103890995893380022607743740081787109376
82. 2576576769103890995893380022607743740081787109376
83. 7423423230896109004106619977392256259918212890625
84. 42576576769103890995893380022607743740081787109376
85. 57423423230896109004106619977392256259918212890625
86. 442576576769103890995893380022607743740081787109376
87. 557423423230896109004106619977392256259918212890625
88. 9442576576769103890995893380022607743740081787109376
89. 99442576576769103890995893380022607743740081787109376
90. 999442576576769103890995893380022607743740081787109376
91. 1000557423423230896109004106619977392256259918212890625
92. 8999442576576769103890995893380022607743740081787109376
93. 11000557423423230896109004106619977392256259918212890625
94. 88999442576576769103890995893380022607743740081787109376
95. 188999442576576769103890995893380022607743740081787109376
96. 811000557423423230896109004106619977392256259918212890625
97. 3811000557423423230896109004106619977392256259918212890625
98. 6188999442576576769103890995893380022607743740081787109376
99. 36188999442576576769103890995893380022607743740081787109376

复制代码

wayne

Mathematica代码：

1. hello[digit_, exp_] :=
2. Module[{d = digit, n = exp, tmp},
3. tmp[1] = Block[{k, x, a, nn = n},
4. a /. Solve[a^nn - a == 10 k && 0 < a < 10, {a, k}, Integers]];
5. Union[Flatten[
6. Table[tmp[ii] =
7. Sort[Cases[
8. Flatten@Table[
9. t + 10^(ii - 1) x /.
10. Block[{k, x, a = t},
11. Solve[(a^n - a)/10^(ii - 1) + x (a^(n - 1) n - 1) ==
12. 10 k && 0 <= x < 10, {x, k}, Integers]], {t,
13. tmp[ii - 1]}], _Integer]], {ii, 2, d}]]]]

复制代码

G-Spider

自守数的计算探讨 http://topic.csdn.net/t/20041029/14/3503436.html

wayne

28# G-Spider 不能访问

wayne

1001次幂 100位数有7665个：

1. 1000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000001
2. 1001540347141539266402700165969029103420513334223861976455682337333169637027817196359523418092077057
3. 1003985361783660394122980219875666980838272377998885153153538207781991786760045215487480163574218751
4. 1004474291074800339474319614155303915741214287777252870390779454884838576212137588152996418333704193
5. 1005525708925199660525680385844696084258785712222747129609220545115161423787862411847003581666295807
6. 1006014638216339605877019780124333019161727622001114846846461792218008213239954784512519836425781249
7. 1006992680891830197061490109937833490419136188999442576576769103890995893380022607743740081787109376
8. 1008459652858460733597299834030970896579486665776138023544317662666830362972182803640476581907922943
9. 1009999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999
10. 1010000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000001
11. 1011540347141539266402700165969029103420513334223861976455682337333169637027817196359523418092077057
12. 1013985361783660394122980219875666980838272377998885153153538207781991786760045215487480163574218751
13. 1014474291074800339474319614155303915741214287777252870390779454884838576212137588152996418333704193
14. 1015525708925199660525680385844696084258785712222747129609220545115161423787862411847003581666295807
15. 1016014638216339605877019780124333019161727622001114846846461792218008213239954784512519836425781249
16. 1018459652858460733597299834030970896579486665776138023544317662666830362972182803640476581907922943
17. 1019999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999
18. .....

复制代码