关于自守数

无心人

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. .....

复制代码