Jordan-Pólya numbers: Difference between revisions

Line 159:

i.e. (4!)^8 * (2!)^16

</pre>

=={{header|Phix}}==

with javascript_semantics

function factorials_le(atom limit)

sequence res = {}

while true do

atom nf = factorial(length(res)+1)

if nf>limit then exit end if

res &= nf

end while

return res

end function

function jp(atom limit)

sequence res = factorials_le(limit)

integer k=2

while k<=length(res) do

atom rk = res[k]

for l=2 to length(res) do

atom kl = res[l]*rk

if kl>limit then exit end if

do

integer p = binary_search(kl,res)

if p<0 then

p = abs(p)

res = res[1..p-1] & kl & res[p..$]

end if

kl *= rk

until kl>limit

end for

k += 1

end while

return res

end function

function decompose(atom jp)

atom jp0 = jp

sequence f = factorials_le(jp)

while true do

string res = ""

for i=length(f) to 2 by -1 do

atom fi = f[i]

if remainder(jp,fi)=0 then

jp /= fi

if length(res) then res &= " * " end if

res &= sprintf("%d!",i)

integer fc = 0

while remainder(jp,fi)=0 do

jp /= fi

fc += 1

end while

if fc then

res &= sprintf("^%d",fc+1)

end if

if jp=1 then return res end if

end for

f = f[1..-2]

jp = jp0

end while

end function

atom t0 = time()

sequence r = jp(power(2,53)-1)

printf(1,"%d Jordan-Polya numbers found, the first 50 are:\n%s\n",

{length(r),join_by(r[1..50],1,10," ",fmt:="%4d")})

printf(1,"The largest under 100 million: %,d\n",r[abs(binary_search(1e8,r))-1])

for i in {100,800,1800,2800,3800} do

printf(1,"The %d%s is %,d = %s\n",{i,ord(i),r[i],decompose(r[i])})

end for

?elapsed(time()-t0)

<pre>

3887 Jordan-Polya numbers found, the first 50 are:

1 2 4 6 8 12 16 24 32 36

48 64 72 96 120 128 144 192 216 240

256 288 384 432 480 512 576 720 768 864

960 1024 1152 1296 1440 1536 1728 1920 2048 2304

2592 2880 3072 3456 3840 4096 4320 4608 5040 5184

The largest under 100 million: 99,532,800

The 100th is 92,160 = 6! * 2!^7

The 800th is 18,345,885,696 = 4!^7 * 2!^2

The 1800th is 9,784,472,371,200 = 6!^2 * 4!^2 * 2!^15

The 2800th is 439,378,587,648,000 = 14! * 7!

The 3800th is 7,213,895,789,838,336 = 4!^8 * 2!^16

"0.3s"

</pre>

Actually slightly faster under pwa/p2js than it is on desktop/Phix.

=={{header|Wren}}==

@@ Line 159: / Line 159: @@
   i.e. (4!)^8 * (2!)^16
 </pre>
+=={{header|Phix}}==
+<!--<syntaxhighlight lang="phix">(phixonline)-->
+ <span style="color: #008080;">with</span> <span style="color: #008080;">javascript_semantics</span>
+ <span style="color: #008080;">function</span> <span style="color: #000000;">factorials_le</span><span style="color: #0000FF;">(</span><span style="color: #004080;">atom</span> <span style="color: #000000;">limit</span><span style="color: #0000FF;">)</span>
+     <span style="color: #004080;">sequence</span> <span style="color: #000000;">res</span> <span style="color: #0000FF;">=</span> <span style="color: #0000FF;">{}</span>
+     <span style="color: #008080;">while</span> <span style="color: #004600;">true</span> <span style="color: #008080;">do</span>
+         <span style="color: #004080;">atom</span> <span style="color: #000000;">nf</span> <span style="color: #0000FF;">=</span> <span style="color: #7060A8;">factorial</span><span style="color: #0000FF;">(</span><span style="color: #7060A8;">length</span><span style="color: #0000FF;">(</span><span style="color: #000000;">res</span><span style="color: #0000FF;">)+</span><span style="color: #000000;">1</span><span style="color: #0000FF;">)</span>
+         <span style="color: #008080;">if</span> <span style="color: #000000;">nf</span><span style="color: #0000FF;">></span><span style="color: #000000;">limit</span> <span style="color: #008080;">then</span> <span style="color: #008080;">exit</span> <span style="color: #008080;">end</span> <span style="color: #008080;">if</span>
+         <span style="color: #000000;">res</span> <span style="color: #0000FF;">&=</span> <span style="color: #000000;">nf</span>
+     <span style="color: #008080;">end</span> <span style="color: #008080;">while</span>
+     <span style="color: #008080;">return</span> <span style="color: #000000;">res</span>
+ <span style="color: #008080;">end</span> <span style="color: #008080;">function</span>
+ <span style="color: #008080;">function</span> <span style="color: #000000;">jp</span><span style="color: #0000FF;">(</span><span style="color: #004080;">atom</span> <span style="color: #000000;">limit</span><span style="color: #0000FF;">)</span>
+     <span style="color: #004080;">sequence</span> <span style="color: #000000;">res</span> <span style="color: #0000FF;">=</span> <span style="color: #000000;">factorials_le</span><span style="color: #0000FF;">(</span><span style="color: #000000;">limit</span><span style="color: #0000FF;">)</span>
+     <span style="color: #004080;">integer</span> <span style="color: #000000;">k</span><span style="color: #0000FF;">=</span><span style="color: #000000;">2</span>
+     <span style="color: #008080;">while</span> <span style="color: #000000;">k</span><span style="color: #0000FF;"><=</span><span style="color: #7060A8;">length</span><span style="color: #0000FF;">(</span><span style="color: #000000;">res</span><span style="color: #0000FF;">)</span> <span style="color: #008080;">do</span>
+         <span style="color: #004080;">atom</span> <span style="color: #000000;">rk</span> <span style="color: #0000FF;">=</span> <span style="color: #000000;">res</span><span style="color: #0000FF;">[</span><span style="color: #000000;">k</span><span style="color: #0000FF;">]</span>
+         <span style="color: #008080;">for</span> <span style="color: #000000;">l</span><span style="color: #0000FF;">=</span><span style="color: #000000;">2</span> <span style="color: #008080;">to</span> <span style="color: #7060A8;">length</span><span style="color: #0000FF;">(</span><span style="color: #000000;">res</span><span style="color: #0000FF;">)</span> <span style="color: #008080;">do</span>
+             <span style="color: #004080;">atom</span> <span style="color: #000000;">kl</span> <span style="color: #0000FF;">=</span> <span style="color: #000000;">res</span><span style="color: #0000FF;">[</span><span style="color: #000000;">l</span><span style="color: #0000FF;">]*</span><span style="color: #000000;">rk</span>
+             <span style="color: #008080;">if</span> <span style="color: #000000;">kl</span><span style="color: #0000FF;">></span><span style="color: #000000;">limit</span> <span style="color: #008080;">then</span> <span style="color: #008080;">exit</span> <span style="color: #008080;">end</span> <span style="color: #008080;">if</span>
+             <span style="color: #008080;">do</span>
+                 <span style="color: #004080;">integer</span> <span style="color: #000000;">p</span> <span style="color: #0000FF;">=</span> <span style="color: #7060A8;">binary_search</span><span style="color: #0000FF;">(</span><span style="color: #000000;">kl</span><span style="color: #0000FF;">,</span><span style="color: #000000;">res</span><span style="color: #0000FF;">)</span>
+                 <span style="color: #008080;">if</span> <span style="color: #000000;">p</span><span style="color: #0000FF;"><</span><span style="color: #000000;">0</span> <span style="color: #008080;">then</span>
+                     <span style="color: #000000;">p</span> <span style="color: #0000FF;">=</span> <span style="color: #7060A8;">abs</span><span style="color: #0000FF;">(</span><span style="color: #000000;">p</span><span style="color: #0000FF;">)</span>
+                     <span style="color: #000000;">res</span> <span style="color: #0000FF;">=</span> <span style="color: #000000;">res</span><span style="color: #0000FF;">[</span><span style="color: #000000;">1</span><span style="color: #0000FF;">..</span><span style="color: #000000;">p</span><span style="color: #0000FF;">-</span><span style="color: #000000;">1</span><span style="color: #0000FF;">]</span> <span style="color: #0000FF;">&</span> <span style="color: #000000;">kl</span> <span style="color: #0000FF;">&</span> <span style="color: #000000;">res</span><span style="color: #0000FF;">[</span><span style="color: #000000;">p</span><span style="color: #0000FF;">..$]</span>
+                 <span style="color: #008080;">end</span> <span style="color: #008080;">if</span>
+                 <span style="color: #000000;">kl</span> <span style="color: #0000FF;">*=</span> <span style="color: #000000;">rk</span>
+             <span style="color: #008080;">until</span> <span style="color: #000000;">kl</span><span style="color: #0000FF;">></span><span style="color: #000000;">limit</span>
+         <span style="color: #008080;">end</span> <span style="color: #008080;">for</span>
+         <span style="color: #000000;">k</span> <span style="color: #0000FF;">+=</span> <span style="color: #000000;">1</span>
+     <span style="color: #008080;">end</span> <span style="color: #008080;">while</span>
+     <span style="color: #008080;">return</span> <span style="color: #000000;">res</span>
+ <span style="color: #008080;">end</span> <span style="color: #008080;">function</span>
+ <span style="color: #008080;">function</span> <span style="color: #000000;">decompose</span><span style="color: #0000FF;">(</span><span style="color: #004080;">atom</span> <span style="color: #000000;">jp</span><span style="color: #0000FF;">)</span>
+     <span style="color: #004080;">atom</span> <span style="color: #000000;">jp0</span> <span style="color: #0000FF;">=</span> <span style="color: #000000;">jp</span>
+     <span style="color: #004080;">sequence</span> <span style="color: #000000;">f</span> <span style="color: #0000FF;">=</span> <span style="color: #000000;">factorials_le</span><span style="color: #0000FF;">(</span><span style="color: #000000;">jp</span><span style="color: #0000FF;">)</span>
+     <span style="color: #008080;">while</span> <span style="color: #004600;">true</span> <span style="color: #008080;">do</span>
+         <span style="color: #004080;">string</span> <span style="color: #000000;">res</span> <span style="color: #0000FF;">=</span> <span style="color: #008000;">""</span>
+         <span style="color: #008080;">for</span> <span style="color: #000000;">i</span><span style="color: #0000FF;">=</span><span style="color: #7060A8;">length</span><span style="color: #0000FF;">(</span><span style="color: #000000;">f</span><span style="color: #0000FF;">)</span> <span style="color: #008080;">to</span> <span style="color: #000000;">2</span> <span style="color: #008080;">by</span> <span style="color: #0000FF;">-</span><span style="color: #000000;">1</span> <span style="color: #008080;">do</span>
+             <span style="color: #004080;">atom</span> <span style="color: #000000;">fi</span> <span style="color: #0000FF;">=</span> <span style="color: #000000;">f</span><span style="color: #0000FF;">[</span><span style="color: #000000;">i</span><span style="color: #0000FF;">]</span>
+             <span style="color: #008080;">if</span> <span style="color: #7060A8;">remainder</span><span style="color: #0000FF;">(</span><span style="color: #000000;">jp</span><span style="color: #0000FF;">,</span><span style="color: #000000;">fi</span><span style="color: #0000FF;">)=</span><span style="color: #000000;">0</span> <span style="color: #008080;">then</span>
+                 <span style="color: #000000;">jp</span> <span style="color: #0000FF;">/=</span> <span style="color: #000000;">fi</span>
+                 <span style="color: #008080;">if</span> <span style="color: #7060A8;">length</span><span style="color: #0000FF;">(</span><span style="color: #000000;">res</span><span style="color: #0000FF;">)</span> <span style="color: #008080;">then</span> <span style="color: #000000;">res</span> <span style="color: #0000FF;">&=</span> <span style="color: #008000;">" * "</span> <span style="color: #008080;">end</span> <span style="color: #008080;">if</span>
+                 <span style="color: #000000;">res</span> <span style="color: #0000FF;">&=</span> <span style="color: #7060A8;">sprintf</span><span style="color: #0000FF;">(</span><span style="color: #008000;">"%d!"</span><span style="color: #0000FF;">,</span><span style="color: #000000;">i</span><span style="color: #0000FF;">)</span>
+                 <span style="color: #004080;">integer</span> <span style="color: #000000;">fc</span> <span style="color: #0000FF;">=</span> <span style="color: #000000;">0</span>
+                 <span style="color: #008080;">while</span> <span style="color: #7060A8;">remainder</span><span style="color: #0000FF;">(</span><span style="color: #000000;">jp</span><span style="color: #0000FF;">,</span><span style="color: #000000;">fi</span><span style="color: #0000FF;">)=</span><span style="color: #000000;">0</span> <span style="color: #008080;">do</span>
+                     <span style="color: #000000;">jp</span> <span style="color: #0000FF;">/=</span> <span style="color: #000000;">fi</span>
+                     <span style="color: #000000;">fc</span> <span style="color: #0000FF;">+=</span> <span style="color: #000000;">1</span>
+                 <span style="color: #008080;">end</span> <span style="color: #008080;">while</span>
+                 <span style="color: #008080;">if</span> <span style="color: #000000;">fc</span> <span style="color: #008080;">then</span>
+                     <span style="color: #000000;">res</span> <span style="color: #0000FF;">&=</span> <span style="color: #7060A8;">sprintf</span><span style="color: #0000FF;">(</span><span style="color: #008000;">"^%d"</span><span style="color: #0000FF;">,</span><span style="color: #000000;">fc</span><span style="color: #0000FF;">+</span><span style="color: #000000;">1</span><span style="color: #0000FF;">)</span>
+                 <span style="color: #008080;">end</span> <span style="color: #008080;">if</span>
+             <span style="color: #008080;">end</span> <span style="color: #008080;">if</span>
+             <span style="color: #008080;">if</span> <span style="color: #000000;">jp</span><span style="color: #0000FF;">=</span><span style="color: #000000;">1</span> <span style="color: #008080;">then</span> <span style="color: #008080;">return</span> <span style="color: #000000;">res</span> <span style="color: #008080;">end</span> <span style="color: #008080;">if</span>
+         <span style="color: #008080;">end</span> <span style="color: #008080;">for</span>
+         <span style="color: #000000;">f</span> <span style="color: #0000FF;">=</span> <span style="color: #000000;">f</span><span style="color: #0000FF;">[</span><span style="color: #000000;">1</span><span style="color: #0000FF;">..-</span><span style="color: #000000;">2</span><span style="color: #0000FF;">]</span>
+         <span style="color: #000000;">jp</span> <span style="color: #0000FF;">=</span> <span style="color: #000000;">jp0</span>
+     <span style="color: #008080;">end</span> <span style="color: #008080;">while</span>
+ <span style="color: #008080;">end</span> <span style="color: #008080;">function</span>
+ <span style="color: #004080;">atom</span> <span style="color: #000000;">t0</span> <span style="color: #0000FF;">=</span> <span style="color: #7060A8;">time</span><span style="color: #0000FF;">()</span>
+ <span style="color: #004080;">sequence</span> <span style="color: #000000;">r</span> <span style="color: #0000FF;">=</span> <span style="color: #000000;">jp</span><span style="color: #0000FF;">(</span><span style="color: #7060A8;">power</span><span style="color: #0000FF;">(</span><span style="color: #000000;">2</span><span style="color: #0000FF;">,</span><span style="color: #000000;">53</span><span style="color: #0000FF;">)-</span><span style="color: #000000;">1</span><span style="color: #0000FF;">)</span>
+ <span style="color: #7060A8;">printf</span><span style="color: #0000FF;">(</span><span style="color: #000000;">1</span><span style="color: #0000FF;">,</span><span style="color: #008000;">"%d Jordan-Polya numbers found, the first 50 are:\n%s\n"</span><span style="color: #0000FF;">,</span>
+          <span style="color: #0000FF;">{</span><span style="color: #7060A8;">length</span><span style="color: #0000FF;">(</span><span style="color: #000000;">r</span><span style="color: #0000FF;">),</span><span style="color: #7060A8;">join_by</span><span style="color: #0000FF;">(</span><span style="color: #000000;">r</span><span style="color: #0000FF;">[</span><span style="color: #000000;">1</span><span style="color: #0000FF;">..</span><span style="color: #000000;">50</span><span style="color: #0000FF;">],</span><span style="color: #000000;">1</span><span style="color: #0000FF;">,</span><span style="color: #000000;">10</span><span style="color: #0000FF;">,</span><span style="color: #008000;">" "</span><span style="color: #0000FF;">,</span><span style="color: #000000;">fmt</span><span style="color: #0000FF;">:=</span><span style="color: #008000;">"%4d"</span><span style="color: #0000FF;">)})</span>
+ <span style="color: #7060A8;">printf</span><span style="color: #0000FF;">(</span><span style="color: #000000;">1</span><span style="color: #0000FF;">,</span><span style="color: #008000;">"The largest under 100 million: %,d\n"</span><span style="color: #0000FF;">,</span><span style="color: #000000;">r</span><span style="color: #0000FF;">[</span><span style="color: #7060A8;">abs</span><span style="color: #0000FF;">(</span><span style="color: #7060A8;">binary_search</span><span style="color: #0000FF;">(</span><span style="color: #000000;">1e8</span><span style="color: #0000FF;">,</span><span style="color: #000000;">r</span><span style="color: #0000FF;">))-</span><span style="color: #000000;">1</span><span style="color: #0000FF;">])</span>
+ <span style="color: #008080;">for</span> <span style="color: #000000;">i</span> <span style="color: #008080;">in</span> <span style="color: #0000FF;">{</span><span style="color: #000000;">100</span><span style="color: #0000FF;">,</span><span style="color: #000000;">800</span><span style="color: #0000FF;">,</span><span style="color: #000000;">1800</span><span style="color: #0000FF;">,</span><span style="color: #000000;">2800</span><span style="color: #0000FF;">,</span><span style="color: #000000;">3800</span><span style="color: #0000FF;">}</span> <span style="color: #008080;">do</span>
+     <span style="color: #7060A8;">printf</span><span style="color: #0000FF;">(</span><span style="color: #000000;">1</span><span style="color: #0000FF;">,</span><span style="color: #008000;">"The %d%s is %,d = %s\n"</span><span style="color: #0000FF;">,{</span><span style="color: #000000;">i</span><span style="color: #0000FF;">,</span><span style="color: #7060A8;">ord</span><span style="color: #0000FF;">(</span><span style="color: #000000;">i</span><span style="color: #0000FF;">),</span><span style="color: #000000;">r</span><span style="color: #0000FF;">[</span><span style="color: #000000;">i</span><span style="color: #0000FF;">],</span><span style="color: #000000;">decompose</span><span style="color: #0000FF;">(</span><span style="color: #000000;">r</span><span style="color: #0000FF;">[</span><span style="color: #000000;">i</span><span style="color: #0000FF;">])})</span>
+ <span style="color: #008080;">end</span> <span style="color: #008080;">for</span>
+ <span style="color: #0000FF;">?</span><span style="color: #7060A8;">elapsed</span><span style="color: #0000FF;">(</span><span style="color: #7060A8;">time</span><span style="color: #0000FF;">()-</span><span style="color: #000000;">t0</span><span style="color: #0000FF;">)</span>
+<!--</syntaxhighlight>-->
+{{out}}
+<pre>
+ Jordan-Polya numbers found, the first 50 are:
+    2    4    6    8   12   16   24   32   36
+   64   72   96  120  128  144  192  216  240
+  288  384  432  480  512  576  720  768  864
+ 1024 1152 1296 1440 1536 1728 1920 2048 2304
+ 2880 3072 3456 3840 4096 4320 4608 5040 5184
+The largest under 100 million: 99,532,800
+The 100th is 92,160 = 6! * 2!^7
+The 800th is 18,345,885,696 = 4!^7 * 2!^2
+The 1800th is 9,784,472,371,200 = 6!^2 * 4!^2 * 2!^15
+The 2800th is 439,378,587,648,000 = 14! * 7!
+The 3800th is 7,213,895,789,838,336 = 4!^8 * 2!^16
+"0.3s"
+</pre>
+Actually slightly faster under pwa/p2js than it is on desktop/Phix.
 =={{header|Wren}}==