cp's OEIS Frontend

A366472 Irregular triangle read by rows: T(n,k) (n >= 1, k >= 1) = number of increasing geometric progressions in {1,2,3,...,n} of length k with rational ratio.

%I A366472 #14 Mar 28 2025 03:26:37
%S A366472 1,2,1,3,3,4,6,1,5,10,1,6,15,1,7,21,1,8,28,2,1,9,36,4,1,10,45,4,1,11,
%T A366472 55,4,1,12,66,5,1,13,78,5,1,14,91,5,1,15,105,5,1,16,120,8,2,1,17,136,
%U A366472 8,2,1,18,153,10,2,1,19,171,10,2,1,20,190,11,2,1,21,210,11,2,1,22,231,11,2,1,23,253,11,2,1,24,276,12,3,1
%N A366472 Irregular triangle read by rows: T(n,k) (n >= 1, k >= 1) = number of increasing geometric progressions in {1,2,3,...,n} of length k with rational ratio.
%F A366472 T(n,k) = Sum_{p=2..floor(n^(1/(k-1)))} phi(p)*floor(n/p^(k-1)) where phi is the Euler phi-function A000010 and k runs from 1 to 1+floor(log_2(n)).
%e A366472 Triangle begins:
%e A366472   [1],
%e A366472   [2, 1],
%e A366472   [3, 3],
%e A366472   [4, 6, 1],
%e A366472   [5, 10, 1],
%e A366472   [6, 15, 1],
%e A366472   [7, 21, 1],
%e A366472   [8, 28, 2, 1],
%e A366472   [9, 36, 4, 1],
%e A366472   [10, 45, 4, 1],
%e A366472   [11, 55, 4, 1],
%e A366472   [12, 66, 5, 1],
%e A366472   [13, 78, 5, 1],
%e A366472   [14, 91, 5, 1],
%e A366472   [15, 105, 5, 1],
%e A366472   [16, 120, 8, 2, 1],
%e A366472 ...
%p A366472 with(numtheory);
%p A366472 A366472 := proc(n) local v,u2,u1,k,i,p;
%p A366472 v := Array(1..100, 0);
%p A366472 v[1] := n;
%p A366472 u1 := 1+floor(log(n)/log(2));
%p A366472 for k from 2 to u1 do
%p A366472    u2 := floor(n^(1/(k-1)));
%p A366472    v[k] := add(phi(p)*floor(n/p^(k-1)),p=2..u2);
%p A366472   od;
%p A366472 [seq(v[i],i=1..u1)];
%p A366472 end;
%p A366472 for n from 1 to 36 do lprint(A366472(n)); od:
%Y A366472 Row sums give A366471.
%Y A366472 First three columns are A000027, A000217, A132345.
%Y A366472 Cf. A000010.
%K A366472 nonn,tabf
%O A366472 1,2
%A A366472 _Scott R. Shannon_ and _N. J. A. Sloane_, Oct 23 2023