Sequence: smallest number with exactly n divisors: Difference between revisions
Sequence: smallest number with exactly n divisors (view source)
Revision as of 17:09, 13 June 2019
, 5 years ago→Phix: added insane
(→Phix: added insane) |
|||
Line 508:
65->331776
66->46080
</pre>
===insane===
A rather silly (but successful) attempt to reverse engineer all the rules up to 2000.<br>
I got it down to just 11 of them, with only 1 being a complete fudge. Obviously, the
fewer cases each covers, the less sound it is, and those mini-tables for np/p2/p3/p5
and adj are not exactly, um, scientific. Completes in about 0.1s
{{libheader|mpfr}}
<lang Phix>include mpfr.e
mpz r = mpz_init(),
pn = mpz_init()
sequence rule_names = {},
rule_counts = {}
for i=1 to 2000 do
sequence pf = prime_factors(i,true), ri, adj
integer lf = length(pf), np, p2, p3, p5, p, e
string what
if lf>10 then ?9/0 end if
if lf<=1 then what = "prime (proper rule)"
np = 1
adj = {i}
elsif pf[$]=2 then what = "2^k (made up rule)"
np = lf-1
p2 = {2,4,4,4,4,4,4,8,8}[np]
p3 = {2,2,2,2,4,4,4,4,4}[np]
np = {2,2,3,4,4,5,6,6,7}[np]
adj = {p2,p3}
elsif pf[$]=3
and pf[$-1]=2 then what = "2^k*3 (made up rule)"
np = lf-1
p2 = {3,3,4,4,4,6,6,6,6}[np]
p3 = {2,2,3,3,3,4,4,4,4}[np]
np = {2,3,3,4,5,5,6,7,8}[np]
adj = {p2,p3}
elsif lf>4
and pf[$-1]=2 then what="2^k*p (made up rule)"
np = lf-1
adj = {0,4}
elsif lf>4
and pf[$]=3
and pf[$-1]=3
and pf[$-2]=2 then what="2^k*3^2*p (made up rule)"
np = lf-4
p3 = {3,3,3,4,4}[np]
p5 = {2,2,2,3,3}[np]
np = {4,5,6,6,7}[np]
adj = {6,p3,p5}
elsif lf>4
and pf[$]=3
and pf[$-2]=3
and pf[$-4]=2 then what="2^k*3^3*p (made up rule)"
np = lf-1
adj = {6}
elsif lf>5
and pf[$]>3
and pf[$-1]=3
and pf[$-4]=3
and pf[2]=3
and (pf[1]=2 or pf[$]>5) then what="2^k*3^4*p (made up rule)"
np = lf
adj = {}
elsif lf>4
and pf[$-1]=3
and pf[$-4]=3
and (lf>5 or pf[$]=3) then what="[2^k]*3^(>=4)*p (made up rule)"
np = lf-1
adj = {9,pf[$]}&reverse(pf[1..$-3]) -- <bsg>
elsif lf>=7
and pf[$]>3
and pf[$-1]=3
and pf[$-2]=2 then what="2^k*3*p (made up rule)"
np = lf-1
adj = {0,4,3}
elsif i=1440
and pf={2,2,2,2,2,3,3,5} then what="1440 (complete fudge)"
-- nothing quite like this, nothing to build any pattern from...
np = 7
adj = {6,5,3,2,2,2,2}
else what="general (proper rule)"
-- (note this incorporates the p^2, (p>2)^k, p*q, and p*m*q rules)
np = lf
adj = {}
end if
ri = get_primes(-np)
for j=1 to length(adj) do
integer aj = adj[j]
if aj!=0 then pf[-j] = aj end if
end for
for j=1 to np do
ri[j] = {ri[j],pf[-j]-1}
end for
string short = "" -- (eg "2^2*3^3" form)
mpz_set_si(r,1) -- (above as big int)
for j=1 to length(ri) do
{p, e} = ri[j]
if length(short) then short &= "*" end if
short &= sprintf("%d",p)
if e!=1 then
short &= sprintf("^%d",{e})
end if
mpz_ui_pow_ui(pn,p,e)
mpz_mul(r,r,pn)
end for
if i<=15 or remainder(i-1,250)>=248 or i=1440 then
string rs = mpz_get_str(r)
if length(rs)>20 then
rs[6..-6] = sprintf("<-- %d digits -->",length(rs)-10)
end if
if short="2^0" then short = "1" end if
printf(1,"%4d : %25s %30s %s\n",{i,short,rs,what})
end if
integer k = find(what,rule_names)
if k=0 then
rule_names = append(rule_names,what)
rule_counts = append(rule_counts,1)
else
rule_counts[k] += 1
end if
end for
integer lr = length(rule_names)
printf(1,"\nrules(%d):\n",lr)
sequence tags = custom_sort(rule_counts, tagset(lr))
for i=1 to lr do
integer ti = tags[-i]
printf(1," %30s:%d\n",{rule_names[ti],rule_counts[ti]})
end for
{r,pn} = mpz_clear({r,pn})</lang>
{{out}}
<pre>
1 : 1 1 prime (proper rule)
2 : 2 2 prime (proper rule)
3 : 2^2 4 prime (proper rule)
4 : 2*3 6 2^k (made up rule)
5 : 2^4 16 prime (proper rule)
6 : 2^2*3 12 2^k*3 (made up rule)
7 : 2^6 64 prime (proper rule)
8 : 2^3*3 24 2^k (made up rule)
9 : 2^2*3^2 36 general (proper rule)
10 : 2^4*3 48 general (proper rule)
11 : 2^10 1024 prime (proper rule)
12 : 2^2*3*5 60 2^k*3 (made up rule)
13 : 2^12 4096 prime (proper rule)
14 : 2^6*3 192 general (proper rule)
15 : 2^4*3^2 144 general (proper rule)
249 : 2^82*3^2 43521<-- 16 digits -->22336 general (proper rule)
250 : 2^4*3^4*5^4*7 5670000 general (proper rule)
499 : 2^498 81834<-- 140 digits -->97344 prime (proper rule)
500 : 2^4*3^4*5^4*7*11 62370000 general (proper rule)
749 : 2^106*3^6 59143<-- 25 digits -->22656 general (proper rule)
750 : 2^4*3^4*5^4*7^2*11 436590000 general (proper rule)
999 : 2^36*3^2*5^2*7^2 757632231014400 general (proper rule)
1000 : 2^4*3^4*5^4*7*11*13 810810000 general (proper rule)
1249 : 2^1248 48465<-- 366 digits -->22656 prime (proper rule)
1250 : 2^4*3^4*5^4*7^4*11 21392910000 general (proper rule)
1440 : 2^5*3^4*5^2*7*11*13*17 1102701600 1440 (complete fudge)
1499 : 2^1498 87686<-- 441 digits -->37344 prime (proper rule)
1500 : 2^4*3^4*5^4*7^2*11*13 5675670000 general (proper rule)
1749 : 2^52*3^10*5^2 66483<-- 12 digits -->57600 general (proper rule)
1750 : 2^6*3^4*5^4*7^4*11 85571640000 general (proper rule)
1999 : 2^1998 28703<-- 592 digits -->57344 prime (proper rule)
2000 : 2^4*3^4*5^4*7*11*13*17 13783770000 general (proper rule)
rules(11):
general (proper rule):1583
prime (proper rule):304
2^k*p (made up rule):59
2^k*3*p (made up rule):9
2^k*3^3*p (made up rule):9
2^k (made up rule):9
2^k*3 (made up rule):9
[2^k]*3^(>=4)*p (made up rule):8
2^k*3^2*p (made up rule):5
2^k*3^4*p (made up rule):4
1440 (complete fudge):1
</pre>
| |||