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)]
$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$
如果用算法求所有解，一种比较快速的方法就是分别求出模$2^n$和$5^n$的所有解，然后用中国剩余定理构造所有解。而其中关于两个模为0的解不需要计算。而对于余下的解，我们可以通过随机法得到。
比如对于模$5^n$,设$gcd(k,4*5^{n-1})=h$,我们随机选择一个不含因子5的数，计算它关于模$5^n$的次数，如果这个次数不是h的倍数，放弃，另外产生一个数，知道产生达到要求的数（由于原根比例很高，通常很快可以找到满足要求的数）。然后如果这个数的次数大于h,那么可以计算它的若干倍使得新的数次数为h.
有了次数为h的一个数，那么它的任意次方就构成了所有解。
真精彩！
wayne你抢我买卖
似乎n次幂的自守数，和n的素因子分解有关系啊
无心人 发表于 2011-6-10 16:32 http://bbs.emath.ac.cn/images/common/back.gif
:lol ，好吧，让我来贴一个给力点的 ， 我喜欢2，就贴22次幂的吧：1
25
76
376
625
9376
90625
109376
890625
2890625
7109376
12890625
87109376
212890625
787109376
1787109376
8212890625
18212890625
81787109376
918212890625
9918212890625
40081787109376
59918212890625
259918212890625
740081787109376
3740081787109376
6259918212890625
43740081787109376
56259918212890625
256259918212890625
743740081787109376
2256259918212890625
7743740081787109376
92256259918212890625
392256259918212890625
607743740081787109376
2607743740081787109376
7392256259918212890625
22607743740081787109376
77392256259918212890625
977392256259918212890625
9977392256259918212890625
19977392256259918212890625
80022607743740081787109376
380022607743740081787109376
619977392256259918212890625
3380022607743740081787109376
6619977392256259918212890625
93380022607743740081787109376
106619977392256259918212890625
893380022607743740081787109376
4106619977392256259918212890625
5893380022607743740081787109376
95893380022607743740081787109376
995893380022607743740081787109376
9004106619977392256259918212890625
90995893380022607743740081787109376
109004106619977392256259918212890625
890995893380022607743740081787109376
3890995893380022607743740081787109376
6109004106619977392256259918212890625
96109004106619977392256259918212890625
103890995893380022607743740081787109376
896109004106619977392256259918212890625
9103890995893380022607743740081787109376
30896109004106619977392256259918212890625
69103890995893380022607743740081787109376
230896109004106619977392256259918212890625
769103890995893380022607743740081787109376
3230896109004106619977392256259918212890625
6769103890995893380022607743740081787109376
23230896109004106619977392256259918212890625
76769103890995893380022607743740081787109376
423230896109004106619977392256259918212890625
576769103890995893380022607743740081787109376
3423230896109004106619977392256259918212890625
6576769103890995893380022607743740081787109376
23423230896109004106619977392256259918212890625
76576769103890995893380022607743740081787109376
423423230896109004106619977392256259918212890625
576576769103890995893380022607743740081787109376
2576576769103890995893380022607743740081787109376
7423423230896109004106619977392256259918212890625
42576576769103890995893380022607743740081787109376
57423423230896109004106619977392256259918212890625
442576576769103890995893380022607743740081787109376
557423423230896109004106619977392256259918212890625
9442576576769103890995893380022607743740081787109376
99442576576769103890995893380022607743740081787109376
999442576576769103890995893380022607743740081787109376
1000557423423230896109004106619977392256259918212890625
8999442576576769103890995893380022607743740081787109376
11000557423423230896109004106619977392256259918212890625
88999442576576769103890995893380022607743740081787109376
188999442576576769103890995893380022607743740081787109376
811000557423423230896109004106619977392256259918212890625
3811000557423423230896109004106619977392256259918212890625
6188999442576576769103890995893380022607743740081787109376
36188999442576576769103890995893380022607743740081787109376
Mathematica代码：hello :=
Module[{d = digit, n = exp, tmp},
tmp = Block[{k, x, a, nn = n},
a /. Solve];
Union[Flatten[
Table =
Sort[Cases[
Flatten@Table[
t + 10^(ii - 1) x /.
Block[{k, x, a = t},
Solve[(a^n - a)/10^(ii - 1) + x (a^(n - 1) n - 1) ==
10 k && 0 <= x < 10, {x, k}, Integers]], {t,
tmp}], _Integer]], {ii, 2, d}]]]]
自守数的计算探讨
http://topic.csdn.net/t/20041029/14/3503436.html
28# G-Spider
不能访问
1001次幂 100位数有7665个：1000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000001
1001540347141539266402700165969029103420513334223861976455682337333169637027817196359523418092077057
1003985361783660394122980219875666980838272377998885153153538207781991786760045215487480163574218751
1004474291074800339474319614155303915741214287777252870390779454884838576212137588152996418333704193
1005525708925199660525680385844696084258785712222747129609220545115161423787862411847003581666295807
1006014638216339605877019780124333019161727622001114846846461792218008213239954784512519836425781249
1006992680891830197061490109937833490419136188999442576576769103890995893380022607743740081787109376
1008459652858460733597299834030970896579486665776138023544317662666830362972182803640476581907922943
1009999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999
1010000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000001
1011540347141539266402700165969029103420513334223861976455682337333169637027817196359523418092077057
1013985361783660394122980219875666980838272377998885153153538207781991786760045215487480163574218751
1014474291074800339474319614155303915741214287777252870390779454884838576212137588152996418333704193
1015525708925199660525680385844696084258785712222747129609220545115161423787862411847003581666295807
1016014638216339605877019780124333019161727622001114846846461792218008213239954784512519836425781249
1018459652858460733597299834030970896579486665776138023544317662666830362972182803640476581907922943
1019999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999
.....