A293462 - OEIS

%I #56 Jan 18 2018 12:22:27

%S 0,1,3,4,8,12,16,19,21,23,25,27,31,37,43,48,54,61,69,77,85,93,101,109,

%T 117,125,131,137,143,149,155,160,166,172,178,182,186,190,194,198,204,

%U 210,216,222,228,234,240,246,250,255,261,267,273,279,285,291,297,303,309,315,323,331,341,350,360

%N Let A_n be a square n X n matrix with entries A_n(i,j)=1 if i+j is a perfect power, and A_n(i,j)=0 otherwise. Then a(n) counts the 1's in A_n.

%C A_n is a binary symmetric Hankel matrix.

%C Lim_{n->infinity} a(n)/n^2 = 0.

%C Proof: It can be seen from the formula that a(n) is bound from above by n*[number of perfect powers <= 2*n]. Powers of any particular number contribute no more than log_2(n) each, and there are no more than sqrt(2n) numbers that contribute anything at all, so a(n) <= n*log_2(n)*sqrt(2n), and a(n)/n^2 <= sqrt(2)*log_2(n)/sqrt(n), which goes to 0 at infinity. - _Andrey Zabolotskiy_, Oct 16 2017

%C Conjecture: The golden ratio/golden conjugate are eigenvalues of A_n if and only if n=6, 8 or 9. This has been verified up to n=500.

%C Conjecture: the sequence increases monotonically. - _Robert G. Wilson v_, Oct 09 2017

%C Where the parity of a(n) switches: 2, 4, 8, 16, 18, 32, 50, 64, 72, 98, 108, 128, 162, 200, 242, 256, 288, 338, 392, 450, 500, 512, 578, 648, 722, 800, 864, 882, 968, etc. Each number that is twice a square is present. - _Robert G. Wilson v_, Oct 09 2017

%H Robert G. Wilson v, <a href="/A293462/b293462.txt">Table of n, a(n) for n = 1..10000</a>

%H Mathematics StackExchange, <a href="https://math.stackexchange.com/questions/2296278/a-frac13-conjecture">A One Third Conjecture</a>

%F a(n) ~ (2/3)*n^(3/2). - _Robert G. Wilson v_, Oct 10 2017

%F a(n) = Sum_{k=1..n} k*A075802(k+1) + Sum_{k=1..n-1} k*A075802(2*n-k+1). - _Andrey Zabolotskiy_, Oct 16 2017

%F a(n) = a(n-1) + 2*(i+n) is a perfect power for i=1..n, + 1 if 2n is a perfect power. - _Robert G. Wilson v_, Nov 23 2017

%e          |0 0 1 0 0|

%e          |0 1 0 0 0|

%e    A_5 = |1 0 0 0 1| and so a(5) = 8.

%e          |0 0 0 1 1|

%e          |0 0 1 1 0|

%t perfectPowerQ[n_] := n == 1 || GCD @@ FactorInteger[n][[All, 2]] > 1; f[n_] := Plus @@ Flatten@ Table[ Boole[ perfectPowerQ[i + j]], {i, n}, {j, n}]; Array[f, 60] (* _Robert G. Wilson v_, Oct 09 2017 *)

%t f[n_] := f[n] = f[n - 1] + 2 Plus @@ Flatten@ Table[ Boole[ perfectPowerQ[i + n]], {i, n - 1}] + If[ perfectPowerQ[2 n], 1, 0]; f[1] = 0; Array[f, 60] (* _Robert G. Wilson v_, Nov 23 2017 *)

%o (PARI) a(n) = sum(i=1, n, sum(j=1, n, ispower(i+j) != 0)); \\ _Michel Marcus_, Oct 09 2017

%Y Cf. A075802, A292918 (analogous sequence built upon A010051 instead of A075802).

%K nonn

%O 1,3

%A _Anthony Hernandez_, Oct 09 2017

%E a(31) onward from _Robert G. Wilson v_, Oct 09 2017