A293462 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.

0, 1, 3, 4, 8, 12, 16, 19, 21, 23, 25, 27, 31, 37, 43, 48, 54, 61, 69, 77, 85, 93, 101, 109, 117, 125, 131, 137, 143, 149, 155, 160, 166, 172, 178, 182, 186, 190, 194, 198, 204, 210, 216, 222, 228, 234, 240, 246, 250, 255, 261, 267, 273, 279, 285, 291, 297, 303, 309, 315, 323, 331, 341, 350, 360

Offset

1,3

Comments

A_n is a binary symmetric Hankel matrix.

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

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

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.

Conjecture: the sequence increases monotonically. - Robert G. Wilson v, Oct 09 2017

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

Links

Robert G. Wilson v, Table of n, a(n) for n = 1..10000

Mathematics StackExchange, A One Third Conjecture

Formula

a(n) ~ (2/3)*n^(3/2). - Robert G. Wilson v, Oct 10 2017

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

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

Example

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

Mathematica

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 *)
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 *)

Prog

(PARI) a(n) = sum(i=1, n, sum(j=1, n, ispower(i+j) != 0)); \\ Michel Marcus, Oct 09 2017

Crossrefs

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

Sequence in context: A120116 A199880 A063227 * A190158 A188217 A138926

Adjacent sequences: A293459 A293460 A293461 * A293463 A293464 A293465

Keyword

nonn

Author

Anthony Hernandez, Oct 09 2017

Extensions

a(31) onward from Robert G. Wilson v, Oct 09 2017

Status

approved