|
|
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.
|
|
1
|
|
|
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
(list;
graph;
refs;
listen;
history;
text;
internal format)
|
|
|
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.
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
|
|
|
FORMULA
|
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
|
|
|
KEYWORD
|
nonn
|
|
AUTHOR
|
|
|
EXTENSIONS
|
|
|
STATUS
|
approved
|
|
|
|