Pairs with common factors: Difference between revisions

Line 86:

Term #1e5: 1,960,299,247

Term #1e6: 196,035,947,609

</pre>

=={{header|Phix}}==

with javascript_semantics

function totient(integer n)

integer tot = n, i = 2

while i*i<=n do

if mod(n,i)=0 then

while true do

n /= i

if mod(n,i)!=0 then exit end if

end while

tot -= tot/i

end if

i += iff(i=2?1:2)

end while

if n>1 then

tot -= tot/n

end if

return tot

end function

constant limit = 1e6

sequence a = repeat(0,limit)

atom sumPhi = 0

for n=1 to limit do

sumPhi += totient(n)

if is_prime(n) then

a[n] = a[n-1]

else

a[n] = n * (n - 1) / 2 + 1 - sumPhi

end if

end for

string j = join_by(a[1..100],1,10,fmt:="%,5d")

printf(1,"Number of pairs with common factors - first one hundred terms:\n%s\n",j)

for l in {1, 10, 1e2, 1e3, 1e4, 1e5, 1e6} do

printf(1,"%22s term: %,d\n", {proper(ordinal(l),"SENTENCE"), a[l]})

end for

<pre>

Number of pairs with common factors - first one hundred terms:

0 0 0 1 1 4 4 7 9 14

14 21 21 28 34 41 41 52 52 63

71 82 82 97 101 114 122 137 137 158

158 173 185 202 212 235 235 254 268 291

291 320 320 343 363 386 386 417 423 452

470 497 497 532 546 577 597 626 626 669

669 700 726 757 773 818 818 853 877 922

922 969 969 1,006 1,040 1,079 1,095 1,148 1,148 1,195

1,221 1,262 1,262 1,321 1,341 1,384 1,414 1,461 1,461 1,526

1,544 1,591 1,623 1,670 1,692 1,755 1,755 1,810 1,848 1,907

First term: 0

Tenth term: 14

One hundredth term: 1,907

One thousandth term: 195,309

Ten thousandth term: 19,597,515

One hundred thousandth term: 1,960,299,247

One millionth term: 196,035,947,609

</pre>

@@ Line 86: / Line 86: @@
 Term #1e5: 1,960,299,247
 Term #1e6: 196,035,947,609
+</pre>
+=={{header|Phix}}==
+<!--<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;">totient</span><span style="color: #0000FF;">(</span><span style="color: #004080;">integer</span> <span style="color: #000000;">n</span><span style="color: #0000FF;">)</span>
+     <span style="color: #004080;">integer</span> <span style="color: #000000;">tot</span> <span style="color: #0000FF;">=</span> <span style="color: #000000;">n</span><span style="color: #0000FF;">,</span> <span style="color: #000000;">i</span> <span style="color: #0000FF;">=</span> <span style="color: #000000;">2</span>
+     <span style="color: #008080;">while</span> <span style="color: #000000;">i</span><span style="color: #0000FF;">*</span><span style="color: #000000;">i</span><span style="color: #0000FF;"><=</span><span style="color: #000000;">n</span> <span style="color: #008080;">do</span>
+         <span style="color: #008080;">if</span> <span style="color: #7060A8;">mod</span><span style="color: #0000FF;">(</span><span style="color: #000000;">n</span><span style="color: #0000FF;">,</span><span style="color: #000000;">i</span><span style="color: #0000FF;">)=</span><span style="color: #000000;">0</span> <span style="color: #008080;">then</span>
+             <span style="color: #008080;">while</span> <span style="color: #004600;">true</span> <span style="color: #008080;">do</span>
+                 <span style="color: #000000;">n</span> <span style="color: #0000FF;">/=</span> <span style="color: #000000;">i</span>
+                 <span style="color: #008080;">if</span> <span style="color: #7060A8;">mod</span><span style="color: #0000FF;">(</span><span style="color: #000000;">n</span><span style="color: #0000FF;">,</span><span style="color: #000000;">i</span><span style="color: #0000FF;">)!=</span><span style="color: #000000;">0</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;">end</span> <span style="color: #008080;">while</span>
+             <span style="color: #000000;">tot</span> <span style="color: #0000FF;">-=</span> <span style="color: #000000;">tot</span><span style="color: #0000FF;">/</span><span style="color: #000000;">i</span>
+         <span style="color: #008080;">end</span> <span style="color: #008080;">if</span>
+         <span style="color: #000000;">i</span> <span style="color: #0000FF;">+=</span> <span style="color: #008080;">iff</span><span style="color: #0000FF;">(</span><span style="color: #000000;">i</span><span style="color: #0000FF;">=</span><span style="color: #000000;">2</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: #008080;">end</span> <span style="color: #008080;">while</span>
+     <span style="color: #008080;">if</span> <span style="color: #000000;">n</span><span style="color: #0000FF;">></span><span style="color: #000000;">1</span> <span style="color: #008080;">then</span>
+         <span style="color: #000000;">tot</span> <span style="color: #0000FF;">-=</span> <span style="color: #000000;">tot</span><span style="color: #0000FF;">/</span><span style="color: #000000;">n</span>
+     <span style="color: #008080;">end</span> <span style="color: #008080;">if</span>
+     <span style="color: #008080;">return</span> <span style="color: #000000;">tot</span>
+ <span style="color: #008080;">end</span> <span style="color: #008080;">function</span>
+ <span style="color: #008080;">constant</span> <span style="color: #000000;">limit</span> <span style="color: #0000FF;">=</span> <span style="color: #000000;">1e6</span>
+ <span style="color: #004080;">sequence</span> <span style="color: #000000;">a</span> <span style="color: #0000FF;">=</span> <span style="color: #7060A8;">repeat</span><span style="color: #0000FF;">(</span><span style="color: #000000;">0</span><span style="color: #0000FF;">,</span><span style="color: #000000;">limit</span><span style="color: #0000FF;">)</span>
+ <span style="color: #004080;">atom</span> <span style="color: #000000;">sumPhi</span> <span style="color: #0000FF;">=</span> <span style="color: #000000;">0</span>
+ <span style="color: #008080;">for</span> <span style="color: #000000;">n</span><span style="color: #0000FF;">=</span><span style="color: #000000;">1</span> <span style="color: #008080;">to</span> <span style="color: #000000;">limit</span> <span style="color: #008080;">do</span>
+     <span style="color: #000000;">sumPhi</span> <span style="color: #0000FF;">+=</span> <span style="color: #000000;">totient</span><span style="color: #0000FF;">(</span><span style="color: #000000;">n</span><span style="color: #0000FF;">)</span>
+     <span style="color: #008080;">if</span> <span style="color: #7060A8;">is_prime</span><span style="color: #0000FF;">(</span><span style="color: #000000;">n</span><span style="color: #0000FF;">)</span> <span style="color: #008080;">then</span>
+         <span style="color: #000000;">a</span><span style="color: #0000FF;">[</span><span style="color: #000000;">n</span><span style="color: #0000FF;">]</span> <span style="color: #0000FF;">=</span> <span style="color: #000000;">a</span><span style="color: #0000FF;">[</span><span style="color: #000000;">n</span><span style="color: #0000FF;">-</span><span style="color: #000000;">1</span><span style="color: #0000FF;">]</span>
+     <span style="color: #008080;">else</span>
+         <span style="color: #000000;">a</span><span style="color: #0000FF;">[</span><span style="color: #000000;">n</span><span style="color: #0000FF;">]</span> <span style="color: #0000FF;">=</span> <span style="color: #000000;">n</span> <span style="color: #0000FF;">*</span> <span style="color: #0000FF;">(</span><span style="color: #000000;">n</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;">2</span> <span style="color: #0000FF;">+</span> <span style="color: #000000;">1</span> <span style="color: #0000FF;">-</span> <span style="color: #000000;">sumPhi</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: #004080;">string</span> <span style="color: #000000;">j</span> <span style="color: #0000FF;">=</span> <span style="color: #7060A8;">join_by</span><span style="color: #0000FF;">(</span><span style="color: #000000;">a</span><span style="color: #0000FF;">[</span><span style="color: #000000;">1</span><span style="color: #0000FF;">..</span><span style="color: #000000;">100</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: #000000;">fmt</span><span style="color: #0000FF;">:=</span><span style="color: #008000;">"%,5d"</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;">"Number of pairs with common factors - first one hundred terms:\n%s\n"</span><span style="color: #0000FF;">,</span><span style="color: #000000;">j</span><span style="color: #0000FF;">)</span>
+ <span style="color: #008080;">for</span> <span style="color: #000000;">l</span> <span style="color: #008080;">in</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: #000000;">1e2</span><span style="color: #0000FF;">,</span> <span style="color: #000000;">1e3</span><span style="color: #0000FF;">,</span> <span style="color: #000000;">1e4</span><span style="color: #0000FF;">,</span> <span style="color: #000000;">1e5</span><span style="color: #0000FF;">,</span> <span style="color: #000000;">1e6</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;">"%22s term: %,d\n"</span><span style="color: #0000FF;">,</span> <span style="color: #0000FF;">{</span><span style="color: #7060A8;">proper</span><span style="color: #0000FF;">(</span><span style="color: #7060A8;">ordinal</span><span style="color: #0000FF;">(</span><span style="color: #000000;">l</span><span style="color: #0000FF;">),</span><span style="color: #008000;">"SENTENCE"</span><span style="color: #0000FF;">),</span> <span style="color: #000000;">a</span><span style="color: #0000FF;">[</span><span style="color: #000000;">l</span><span style="color: #0000FF;">]})</span>
+ <span style="color: #008080;">end</span> <span style="color: #008080;">for</span>
+<!--</lang>-->
+{{out}}
+<pre>
+Number of pairs with common factors - first one hundred terms:
+0       0       1       1       4       4       7       9      14
+21      21      28      34      41      41      52      52      63
+82      82      97     101     114     122     137     137     158
+173     185     202     212     235     235     254     268     291
+320     320     343     363     386     386     417     423     452
+497     497     532     546     577     597     626     626     669
+700     726     757     773     818     818     853     877     922
+969     969   1,006   1,040   1,079   1,095   1,148   1,148   1,195
+,221   1,262   1,262   1,321   1,341   1,384   1,414   1,461   1,461   1,526
+,544   1,591   1,623   1,670   1,692   1,755   1,755   1,810   1,848   1,907
+                 First term: 0
+                 Tenth term: 14
+         One hundredth term: 1,907
+        One thousandth term: 195,309
+        Ten thousandth term: 19,597,515
+One hundred thousandth term: 1,960,299,247
+         One millionth term: 196,035,947,609
 </pre>