%I
%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/afrac13conjecture">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..n1} k*A075802(2*nk+1).  _Andrey Zabolotskiy_, Oct 16 2017
%F a(n) = a(n1) + 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
