Sequence: nth number with exactly n divisors: Difference between revisions
Sequence: nth number with exactly n divisors (view source)
Revision as of 00:11, 14 June 2019
, 5 years ago→{{header|Phix}}
Line 616:
=={{header|Phix}}==
{{libheader|mpfr}}
===simple===
Certainly not the fastest way to do it, hence the relatively small limit of 24, which takes less than 0.4s,<br>
whereas a limit of 25 would need to invoke factors() 52 million times which would no doubt take a fair while.
Line 674 ⟶ 675:
23 : 1658509762573818415340429240403156732495289
24 : 1170
</pre>
===cheating slightly===
No real patterns that I could see here, but you can still identify and single out the troublemakers.
<lang Phix>include mpfr.e
atom t0 = time()
constant LIMIT = 100
include mpfr.e
include primes.e
mpz z = mpz_init(),
p = mpz_init()
string mz
sequence fn = 1&repeat(0,LIMIT-1)
integer k = 1, dx, p1, p2
printf(1,"The first %d terms in the sequence are:\n",LIMIT)
for i=1 to LIMIT do
if is_prime(i) or i=1 then
mpz_ui_pow_ui(z,get_prime(i),i-1)
mz = mpz_get_str(z)
else
sequence f = prime_factors(i,1)
if length(f)=2 and f[1]=2 and f[2]>7 then
mz = sprintf("%d",power(2,f[2]-1)*get_prime(i+1))
elsif length(f)=2 and f[1]>2 then
if f[1]=f[2] then
mz = sprintf("%d",power(f[1]*get_prime(f[1]+2),f[1]-1))
else -- deal with some tardy ones...
dx = find(i,{15,21,33,35,39,51,55,57,65,69,77,85,87,91,93,95})
p1 = {3,2,2,5,2,2,2,2,2,2,7,2,2,7,2,2}[dx]
p2 = {5,15,29,6,35,49,34,56,45,69,7,65,88,7,94,77}[dx]
mpz_ui_pow_ui(z,p1,f[2]-1)
mpz_ui_pow_ui(p,get_prime(p2),f[1]-1)
mpz_mul(z,z,p)
mz = mpz_get_str(z)
end if
elsif (length(f)=3 and i>50) or (length(f)=4 and (f[1]=3 or f[4]>7)) then
if i=99 then -- (oops, messed that one up!)
mz = sprintf("%d",4*power(3,10)*31*31)
elsif i=63 then -- (and another!)
mz = sprintf("%d",power(2,8)*power(5,6))
else
dx = find(i,{52,66,68,70,75,76,78,92,98,81,88})
p1 = { 7, 3, 1, 5, 3, 5, 5,13, 3,35,35}[dx]
p2 = { 1, 2, 1, 4, 4, 1, 2, 1, 1, 2, 1}[dx]
mpz_ui_pow_ui(z,2,f[$]-1)
mpz_ui_pow_ui(p,p1,p2)
mpz_mul(z,z,p)
p1 = {13,37, 4, 9,34,22,19,12, 4,11,13}[dx]
p2 = { 1, 1, 3, 1, 2, 1, 1, 1, 6, 2, 1}[dx]
mpz_ui_pow_ui(p,get_prime(p1),p2)
mpz_mul(z,z,p)
mz = mpz_get_str(z)
end if
else
while fn[i]<i do
k += 1
integer l = length(factors(k,1))
if l<=LIMIT and fn[l]<l then
fn[l] = iff(fn[l]+1<l?fn[l]+1:k)
end if
end while
mz = sprintf("%d",fn[i])
end if
end if
printf(1,"%3d : %s\n",{i,mz})
end for
printf(1,"completed in %s\n",{elapsed(time()-t0)})</lang>
{{out}}
<pre>
The first 100 terms in the sequence are:
1 : 1
2 : 3
3 : 25
4 : 14
5 : 14641
6 : 44
7 : 24137569
8 : 70
9 : 1089
10 : 405
11 : 819628286980801
12 : 160
13 : 22563490300366186081
14 : 2752
15 : 9801
16 : 462
17 : 21559177407076402401757871041
18 : 1044
19 : 740195513856780056217081017732809
20 : 1520
21 : 141376
22 : 84992
23 : 1658509762573818415340429240403156732495289
24 : 1170
25 : 52200625
26 : 421888
27 : 52900
28 : 9152
29 : 1116713952456127112240969687448211536647543601817400964721
30 : 6768
31 : 1300503809464370725741704158412711229899345159119325157292552449
32 : 3990
33 : 12166144
34 : 9764864
35 : 446265625
36 : 5472
37 : 11282036144040442334289838466416927162302790252609308623697164994458730076798801
38 : 43778048
39 : 90935296
40 : 10416
41 : 1300532588674810624476094551095787816112173600565095470117230812218524514342511947837104801
42 : 46400
43 : 635918448514386699807643535977466343285944704172890141356181792680152445568879925105775366910081
44 : 240640
45 : 327184
46 : 884998144
47 : 82602452843197830915655434062758747152610200533183747995128511868250464749389571755574391210629602061883161
48 : 10296
49 : 17416274304961
50 : 231984
51 : 3377004544
52 : 1175552
53 : 7326325566540660915295202005885275873916026034616342139474905237555535331121749053330837020397976615915057535109963186790081
54 : 62208
55 : 382260265984
56 : 63168
57 : 18132238336
58 : 74356621312
59 : 4611334279555550707926152839105934955536765902552873727962394200823974159354935875908492026570361080937000929065119751494662472171586496615769
60 : 37200
61 : 1279929743416851311019131209907830943453757487243270654630811620734985849511676634764875391422075025095805774223361200187655617244608064273703030801
62 : 329638739968
63 : 4000000
64 : 41160
65 : 6169143218176
66 : 1446912
67 : 20353897784481135224502113429729640062994484338530413467091588021107086251737634020247647652000753728181181145357697865506347474542010115076391004870941216126804332281
68 : 22478848
69 : 505031950336
70 : 920000
71 : 22091712217028661091647719716134154062183987922906664635563029317259865249987461330814689139636373404600637581380931231750650949001643115899851798743405544731506806491024751606849
72 : 48300
73 : 45285235038445046669368642612544904396805516154393281169675637706411327508046898517381759728413013085702957690245765106506995874808813788844198933536768701568785385215106907990288684161
74 : 26044681682944
75 : 25040016
76 : 103546880
77 : 6818265813529681
78 : 6860800
79 : 110984176612396876252402058909207317796166059426692518840795949938301678339569859458072604697803922487329059012193474923358078243829751108364014428972188856355641430510895584045477184112155202949344511201
80 : 96720
81 : 4708900
82 : 473889511571456
83 : 1064476683917919713953093000677954858036756167846865592483240200233630032347646244510522542053167377047784795269272961130616738371982635464615430562192693194769301221853619917764723198332349478419665523610384617408161
84 : 225216
85 : 629009610244096
86 : 1974722883485696
87 : 56062476550144
88 : 1469440
89 : 2544962774801294304714624882135254894108219227449639770372304502957346499018390075803907657903246999131414158076182409047363202723848127272231619125736007088495905384436604400674375401897829996007586872027878808309385140119563002941281
90 : 352512
91 : 334095024862954369
92 : 2017460224
93 : 258858752671744
94 : 35114003344654336
95 : 6002585119227904
96 : 112860
97 : 69969231567692157576407845029145070949540195647704307603423555494283752374775631665902846216473259715737953596002226233187827382886325202177640164868195792546734599315840795700630834939445407388277880586442087150607690134279001258366485550281200590593848327041
98 : 22588608
99 : 226984356
100 : 870000
completed in 4.4s
</pre>
| |||