Pairs with common factors
Generate the sequence where each term n is the count of the pairs (x,y) with 1 < x < y <= n, that have at least one common prime factor.
For instance, when n = 9, examine the pairs:
(2,3) (2,4) (2,5) (2,6) (2,7) (2,8) (2,9) (3,4) (3,5) (3,6) (3,7) (3,8) (3,9) (4,5) (4,6) (4,7) (4,8) (4,9) (5,6) (5,7) (5,8) (5,9) (6,7) (6,8) (6,9) (7,8) (7,9) (8,9)
Find all of the pairs that have at least one common prime factor:
(2,4) (2,6) (2,8) (3,6) (3,9) (4,6) (4,8) (6,8) (6,9)
and count them:
a(9) = 9
Terms may be found directly using the formula:
a(n) = n × (n-1) / 2 + 1 - 𝚺{i=1..n} 𝚽(i)
where 𝚽() is Phi; the Euler totient function.
For the term a(p), if p is prime, then a(p) is equal to the previous term.
- Task
- Find and display the first one hundred terms of the sequence.
- Find and display the one thousandth.
- Stretch
- Find and display the ten thousandth, one hundred thousandth, one millionth.
- See also
Factor[edit]
USING: formatting grouping io kernel math math.functions
math.primes.factors prettyprint ranges sequences
tools.memory.private ;
: totient-sum ( n -- sum )
[1..b] [ totient ] map-sum ;
: a ( n -- a(n) )
dup [ 1 - * 2 / ] keep totient-sum - ;
"Number of pairs with common factors - first 100 terms:" print
100 [1..b] [ a commas ] map 10 group simple-table. nl
7 <iota> [ dup 10^ a commas "Term #1e%d: %s\n" printf ] each
- Output:
Number of pairs with common factors - first 100 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 Term #1e0: 0 Term #1e1: 14 Term #1e2: 1,907 Term #1e3: 195,309 Term #1e4: 19,597,515 Term #1e5: 1,960,299,247 Term #1e6: 196,035,947,609
FreeBASIC[edit]
Function isPrime(n As Uinteger) As Boolean
If n Mod 2 = 0 Then Return false
For i As Uinteger = 3 To Int(Sqr(n))+1 Step 2
If n Mod i = 0 Then Return false
Next i
Return true
End Function
Function Totient(n As Uinteger) As Integer
Dim As Uinteger tot = n, i = 2
While i*i <= n
If n Mod i = 0 Then
Do
n /= i
Loop Until n Mod i <> 0
tot -= tot/i
End If
i += Iif(i = 2, 1, 2)
Wend
If n > 1 Then tot -= tot/n
Return tot
End Function
Dim As Uinteger n, limit = 1e6, sumPhi = 0
Dim As Uinteger a(limit)
For n = 1 To limit
sumPhi += Totient(n)
a(n) = Iif(isPrime(n), a(n-1), n * (n - 1) / 2 + 1 - sumPhi)
Next n
Print "Number of pairs with common factors - first one hundred terms:"
Dim As Uinteger j, count = 0
For j = 1 To 100
count += 1
Print Using " ##,###"; a(j);
If(count Mod 10) = 0 Then Print
Next j
Print !"\nThe 1st term: "; a(1)
Print "The 10th term: "; a(10)
Print "The 100th term: "; a(1e2)
Print "The 1,000th term: "; a(1e3)
Print "The 10,000th term: "; a(1e4)
Print "The 100,000th term: "; a(1e5)
Print "The 1,000,000th term: "; a(1e6)
Sleep
- Output:
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 The 1st term: 0 The 10th term: 14 The 100th term: 1907 The 1,000th term: 195309 The 10,000th term: 19597515 The 100,000th term: 1960299247 The 1,000,000th term: 196035947609
J[edit]
For this task, because of the summation of euler totient values, it's more efficient to generate the sequence with a slightly different routine than we would use to compute a single value. Thus: (1 _1r2 1r2&p. - +/\@:(5&p:)) 1+i.1e2
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 1006 1040 1079 1095 1148 1148 1195 1221 1262 1262 1321 1341 1384 1414 1461 1461 1526 1544 1591 1623 1670 1692 1755 1755 1810 1848 1907
(1 _1r2 1r2&p.@{: - +/@:(5&p:)) 1+i.1e3
195309
(1 _1r2 1r2&p.@{: - +/@:(5&p:)) 1+i.1e4
19597515
(1 _1r2 1r2&p.@{: - +/@:(5&p:)) 1+i.1e5
1960299247
(1 _1r2 1r2&p.@{: - +/@:(5&p:)) 1+i.1e6
196035947609
Here, p.
calculates a polynomial (1 + (-x)/2 + (x^2)/2 in this example), 5&p:
is euler's totient function, @{:
modifies the polynomial to only operate on the final element of a sequence, +/
is sum and +/\
is running sum, and 1+i.n
is the sequence of numbers 1 through n.
jq[edit]
Works with jq and gojq, that is, the C and Go implementations of jq.
If using jq, the definition of `_nwise` can be omitted.
Preliminaries
# For the sake of gojq
def _nwise($n):
def n: if length <= $n then . else .[0:$n] , (.[$n:] | n) end;
n;
def lpad($len): tostring | ($len - length) as $l | (" " * $l)[:$l] + .;
def is_prime:
. as $n
| if ($n < 2) then false
elif ($n % 2 == 0) then $n == 2
elif ($n % 3 == 0) then $n == 3
elif ($n % 5 == 0) then $n == 5
elif ($n % 7 == 0) then $n == 7
elif ($n % 11 == 0) then $n == 11
elif ($n % 13 == 0) then $n == 13
elif ($n % 17 == 0) then $n == 17
elif ($n % 19 == 0) then $n == 19
else
($n | sqrt) as $rt
| 23
| until( . > $rt or ($n % . == 0); .+2)
| . > $rt
end;
# jq optimizes the recursive call of _gcd in the following:
def gcd(a;b):
def _gcd:
if .[1] != 0 then [.[1], .[0] % .[1]] | _gcd else .[0] end;
[a,b] | _gcd ;
def count(s): reduce s as $x (0; .+1);
def totient:
. as $n
| count( range(0; .) | select( gcd($n; .) == 1) );
The Task
def sumPhi($max):
reduce range(1; max+1) as $n ({};
.sumPhi += ($n|totient)
| if $n | is_prime
then .a[$n-1] = .a[$n-2]
else
.a[$n-1] = $n * ($n - 1) / 2 + 1 - .sumPhi
end ) ;
def limits: [ 1, 10, 1e2, 1e3 ];
"Number of pairs with common factors - first one hundred terms:",
(sumPhi( limits[-1] )
| (.a[0:100] | _nwise(10) | map(lpad(6)) | join(" ") ),
( limits[] as $i
| "The #\($i) term: \(.a[$i-1])" ) )
- Output:
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 1006 1040 1079 1095 1148 1148 1195 1221 1262 1262 1321 1341 1384 1414 1461 1461 1526 1544 1591 1623 1670 1692 1755 1755 1810 1848 1907 The #1 term: 0 The #10 term: 14 The #100 term: 1907 The #1000 term: 195309
Julia[edit]
using Formatting
using Primes
pcf(n) = n * (n - 1) ÷ 2 + 1 - sum(totient, 1:n)
foreach(p -> print(rpad(p[2], 5), p[1] % 20 == 0 ? "\n" : ""), pairs(map(pcf, 1:100)))
for expo in 1:6
println("The ", format(10^expo, commas = true), "th pair with common factors count is ",
format(pcf(10^expo), commas = true))
end
- Output:
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 1006 1040 1079 1095 1148 1148 1195 1221 1262 1262 1321 1341 1384 1414 1461 1461 1526 1544 1591 1623 1670 1692 1755 1755 1810 1848 1907 The 10th pair with common factors count is 14 The 100th pair with common factors count is 1,907 The 1,000th pair with common factors count is 195,309 The 10,000th pair with common factors count is 19,597,515 The 100,000th pair with common factors count is 1,960,299,247 The 1,000,000th pair with common factors count is 196,035,947,609
Pascal[edit]
Free Pascal[edit]
modified Perfect_totient_numbers
program PairsWithCommonFactors;
{$IFdef FPC} {$MODE DELPHI} {$Optimization ON,ALL}{$IFEND}
{$IFdef Windows} {$APPTYPE CONSOLE}{$IFEND}
const
cLimit = 1000*1000*1000;
//global
type
TElem= Uint64;
tpElem = pUint64;
myString = String[31];
var
TotientList : array of TElem;
Sieve : Array of byte;
function Numb2USA(n:Uint64):myString;
const
//extend s by the count of comma to be inserted
deltaLength : array[0..24] of byte =
(0,0,0,0,1,1,1,2,2,2,3,3,3,4,4,4,5,5,5,6,6,6,7,7,7);
var
pI :pChar;
i,j : NativeInt;
Begin
str(n,result);
i := length(result);
//extend s by the count of comma to be inserted
// j := i+ (i-1) div 3;
j := i+deltaLength[i];
if i<> j then
Begin
setlength(result,j);
pI := @result[1];
dec(pI);
while i > 3 do
Begin
//copy 3 digits
pI[j] := pI[i];
pI[j-1] := pI[i-1];
pI[j-2] := pI[i-2];
// insert comma
pI[j-3] := ',';
dec(i,3);
dec(j,4);
end;
end;
end;
procedure SieveInit(svLimit:NativeUint);
var
pSieve:pByte;
i,j,pr :NativeUint;
Begin
svlimit := (svLimit+1) DIV 2;
setlength(sieve,svlimit+1);
pSieve := @Sieve[0];
For i := 1 to svlimit do
Begin
IF pSieve[i]= 0 then
Begin
pr := 2*i+1;
j := (sqr(pr)-1) DIV 2;
IF j> svlimit then
BREAK;
repeat
pSieve[j]:= 1;
inc(j,pr);
until j> svlimit;
end;
end;
pr := 0;
j := 0;
For i := 1 to svlimit do
Begin
IF pSieve[i]= 0 then
Begin
pSieve[j] := i-pr;
inc(j);
pr := i;
end;
end;
setlength(sieve,j);
end;
procedure TotientInit(len: NativeUint);
var
pTotLst : tpElem;
pSieve : pByte;
i: NativeInt;
p,j,k,svLimit : NativeUint;
Begin
SieveInit(len);
setlength(TotientList,len+12);
pTotLst := @TotientList[0];
//Fill totient with simple start values for odd and even numbers
//and multiples of 3
j := 1;
k := 1;// k == j DIV 2
p := 1;// p == j div 3;
repeat
pTotLst[j] := j;//1
pTotLst[j+1] := k;//2 j DIV 2; //2
inc(k);
inc(j,2);
pTotLst[j] := j-p;//3
inc(p);
pTotLst[j+1] := k;//4 j div 2
inc(k);
inc(j,2);
pTotLst[j] := j;//5
pTotLst[j+1] := p;//6 j DIV 3 <= (div 2) * 2 DIV/3
inc(j,2);
inc(p);
inc(k);
until j>len+6;
//correct values of totient by prime factors
svLimit := High(sieve);
p := 3;// starting after 3
pSieve := @Sieve[svLimit+1];
i := -svlimit;
repeat
p := p+2*pSieve[i];
j := p;
while j <= cLimit do
Begin
k:= pTotLst[j];
pTotLst[j]:= k-(k DIV p);
inc(j,p);
end;
inc(i);
until i=0;
//primes not needed anymore
setlength(sieve,0);
end;
procedure CountOfPairs(len: NativeUint);
var
pTotLst : tpElem;
i,a_n,sum,Totient: tElem;
Begin
pTotLst := @TotientList[0];
sum := 1;
a_n := 2; // sums to i*(i-1)/2 +1
For i := 2 to len do
Begin
Totient := pTotLst[i];// relict for print data
sum += Totient;
pTotLst[i] := a_n-sum;
a_n += i;
end;
TotientList[1] := 0;
end;
var
i,k : NativeUint;
Begin
TotientInit(climit);
CountOfPairs(climit);
i := 1;
Repeat
For k := 9 downto 0 do
begin
write(TotientList[i]:6);
inc(i);
end;
writeln;
until i>99;
writeln;
writeln('Some values #');
i := 10;
repeat
writeln(Numb2USA(i):13,Numb2USA(TotientList[i]):25);
i *= 10;
until i > climit;
end.
- Output:
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 1006 1040 1079 1095 1148 1148 1195 1221 1262 1262 1321 1341 1384 1414 1461 1461 1526 1544 1591 1623 1670 1692 1755 1755 1810 1848 1907 Some values # 10 14 100 1,907 1,000 195,309 10,000 19,597,515 100,000 1,960,299,247 1,000,000 196,035,947,609 10,000,000 19,603,638,572,759 100,000,000 1,960,364,433,634,093 1,000,000,000 196,036,448,326,991,587 real 0m23,577s
Perl[edit]
use v5.36;
use ntheory 'factor';
use List::Util qw<sum product uniq max>;
sub comma { reverse ((reverse shift) =~ s/(.{3})/$1,/gr) =~ s/^,//r }
sub table ($c, @V) { my $t = $c * (my $w = 2 + max map {length} @V); ( sprintf( ('%'.$w.'s')x@V, @V) ) =~ s/.{1,$t}\K/\n/gr }
my($max, @phi, @n_pairs) = (100, 0);
for my $t (1..$max) { push @phi, $t * product map { 1 - 1/$_ } uniq factor($t) }
push @n_pairs, comma $_ * ($_ - 1) / 2 + 1 - sum @phi[1..$_] for 1..$max;
say 'Number of pairs with common factors - first one hundred terms:';
say table 10, @n_pairs;
- Output:
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
Phix[edit]
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
- Output:
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
Raku[edit]
use Prime::Factor;
use Lingua::EN::Numbers;
my \𝜑 = 0, |(1..*).hyper.map: -> \t { t × [×] t.&prime-factors.unique.map: { 1 - 1/$_ } }
sub pair-count (\n) { n × (n - 1) / 2 + 1 - sum 𝜑[1..n] }
say "Number of pairs with common factors - first one hundred terms:\n"
~ (1..100).map(&pair-count).batch(10)».&comma».fmt("%6s").join("\n") ~ "\n";
for ^7 { say (my $i = 10 ** $_).&ordinal.tc.fmt("%22s term: ") ~ $i.&pair-count.&comma }
- Output:
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
RPL[edit]
The PHI
function comes from the totient function task.
To save time, Σφ(j) are stored in a global variable named ΣPHI
, which must be initialized at { 1 }
once.
RPL code | Comment |
---|---|
≪ DUP 2 OVER √ FOR j IF DUP j MOD NOT THEN WHILE DUP j MOD NOT REPEAT j / END SWAP DUP j / - SWAP END IF j 2 == THEN 1 'j' STO END 2 STEP IF DUP 1 > THEN OVER SWAP / - ELSE DROP END ≫ ‘PHI’ STO ≪ ∑PHI SIZE IF DUP2 ≤ THEN DROP ELSE '∑PHI' OVER GET SWAP 1 + ∑PHI SWAP 4 ROLL FOR j SWAP j PHI + SWAP OVER + NEXT '∑PHI' STO DROP ∑PHI SIZE END '∑PHI' SWAP GET ≫ '→∑PHI' STO ≪ DUP DUP 1 - * 2 / 1 + SWAP →∑PHI - ≫ ‘A185670’ STO |
PHI ( n -- φ(n) ) Translation of C version →∑PHI ( n -- φ(n) ) if n... ...is not already in ∑PHI initialize stack and loop, for size(∑PHI)+1 to n sum += φ(n), append sum to list store list into ∑PHI read ∑PHI[n] A185670 ( n -- n*(n-1)/2 + 1 - Σφ(j) ) |
- Input:
≪ { } 1 100 FOR j j A185670 + NEXT ≫ EVAL 1000 A185670
- Output:
2: { 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 1006 1040 1079 1095 1148 1148 1195 1221 1262 1262 1321 1341 1384 1414 1461 1461 1526 1544 1591 1623 1670 1692 1755 1755 1810 1848 1907 } 1: 195309
Ruby[edit]
require "prime"
def 𝜑(n) = n.prime_division.inject(1) {|res, (pr, exp)| res *= (pr-1) * pr**(exp-1) }
def a(n) = n*(n-1)/2 + 1 - (1..n).sum{|i| 𝜑(i)}
puts "Number of pairs with common factors - first 100 terms: "
puts (1..100).map{|n| a(n) }.join(", ")
(1..6).each{|e| puts "Term #1e#{e}: #{a(10**e)}"}
- Output:
Number of pairs with common factors - first 100 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, 1006, 1040, 1079, 1095, 1148, 1148, 1195, 1221, 1262, 1262, 1321, 1341, 1384, 1414, 1461, 1461, 1526, 1544, 1591, 1623, 1670, 1692, 1755, 1755, 1810, 1848, 1907 1e1: 14 1e2: 1907 1e3: 195309 1e4: 19597515 1e5: 1960299247 1e6: 196035947609
Wren[edit]
import "./math" for Int
import "./fmt" for Fmt
var totient = Fn.new { |n|
var tot = n
var i = 2
while (i*i <= n) {
if (n%i == 0) {
while(n%i == 0) n = (n/i).floor
tot = tot - (tot/i).floor
}
if (i == 2) i = 1
i = i + 2
}
if (n > 1) tot = tot - (tot/n).floor
return tot
}
var max = 1e6
var a = List.filled(max, 0)
var sumPhi = 0
for (n in 1..max) {
sumPhi = sumPhi + totient.call(n)
if (Int.isPrime(n)) {
a[n-1] = a[n-2]
} else {
a[n-1] = n * (n - 1) / 2 + 1 - sumPhi
}
}
System.print("Number of pairs with common factors - first one hundred terms:")
Fmt.tprint("$,5d ", a[0..99], 10)
System.print()
var limits = [1, 10, 1e2, 1e3, 1e4, 1e5, 1e6]
for (limit in limits) {
Fmt.print("The $,r term: $,d", limit, a[limit-1])
}
- Output:
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 The 1st term: 0 The 10th term: 14 The 100th term: 1,907 The 1,000th term: 195,309 The 10,000th term: 19,597,515 The 100,000th term: 1,960,299,247 The 1,000,000th term: 196,035,947,609