login
Number of distinct terms i^j for 2 <= i,j <= n.
4

%I #40 Feb 11 2024 12:39:48

%S 1,4,8,15,23,34,44,54,69,88,106,129,152,177,195,226,256,291,324,361,

%T 399,442,483,519,564,600,648,703,755,814,856,915,976,1039,1085,1156,

%U 1224,1295,1365,1444,1519,1602,1681,1762,1846,1937,2023,2095,2184,2279

%N Number of distinct terms i^j for 2 <= i,j <= n.

%C An easy upper bound is (n-1)^2 = A000290(n-1).

%H Eric M. Schmidt, <a href="/A126255/b126255.txt">Table of n, a(n) for n = 2..10000</a>

%H Project Euler, <a href="https://projecteuler.net/problem=29">Problem 29: Distinct powers</a>.

%e a(4) = 8 as there are 8 distinct terms in 2^2=4, 2^3=8, 2^4=16, 3^2=9, 3^3=27, 3^4=81, 4^2=16, 4^3=64, 4^4=256.

%t SetAttributes[a, {Listable, NumericFunction}]

%t a[n_ /; n < 2] := "error"

%t a[2] := 1

%t a[n_Integer?IntegerQ /; n > 2] :=

%t Length[DeleteDuplicates[

%t Distribute[f[Range[2, n], Range[2, n]], List,

%t f] /. {f ->

%t Power}]](*By using Distribute instead of Outer I avoid having to use Flatten on Outer*)

%t a[Range[2, 100]]

%t (* _Peter Cullen Burbery_, Aug 15 2023 *)

%o (PARI) lim=51; z=listcreate((lim-1)^2); for(m=2, lim, for(i=2, m, x=factor(i); x[, 2]*=m; s=Str(x); f=setsearch(z, s, 1); if(f, listinsert(z, s, f))); t=factor(m); for(j=2, m, x=t; x[, 2]=j*t[, 2]; s=Str(x); f=setsearch(z, s, 1); if(f, listinsert(z, s, f))); print1(#z, ", "))

%o (Python)

%o def A126255(n): return len({i**j for i in range(2,n+1) for j in range(2,n+1)}) # _Chai Wah Wu_, Oct 17 2023

%Y Cf. A027424, A061786, A126254, A126256, A126257.

%K easy,nonn

%O 2,2

%A _Nick Hobson_, Dec 24 2006