OFFSET
1,4
COMMENTS
Shakov proves that the number of occurrences of k in this sequence is equal to the number of divisors of k^2+1.
It is a 2-regular sequence.
LINKS
Rémy Sigrist, Table of n, a(n) for n = 1..8191
Shreyansh Jaiswal, Colored scatterplot of a(n) based on n modulo 4
Anton Shakov, Polynomials in Z[x] whose divisors are enumerated by SL_2(N_0), arXiv:2405.03552 [math.NT], 2024.
Anton Shakov, A 2-Regular Sequence That Counts The Divisors of n^2+1, arXiv:2510.22805 [math.NT], 2025.
FORMULA
a(n) obeys the recurrences:
a(4*n) = 2*a(2*n) - a(n)
a(4*n+1) = 2*a(2*n) + a(2*n+1)
a(4*n+2) = 2*a(2*n+1) + a(2*n)
a(4*n+3) = 2*a(2*n+1) - a(n)
and a(1) = 0, a(2) = 1, a(3) = 1.
EXAMPLE
For example, 7 occurs at indices 9, 14, 23, 24, 128, 255, and there are 6 divisors of 7^2+1 = 50.
MAPLE
f:= proc(n) option remember; local m, k;
m:= n mod 4;
k:= (n-m)/4;
if m = 0 then 2*procname(2*k) - procname(k)
elif m = 1 then 2*procname(2*k) + procname(2*k+1)
elif m = 2 then 2*procname(2*k+1)+procname(2*k)
else 2*procname(2*k+1)-procname(k)
fi;
end proc:
f(1):= 0: f(2):= 1: f(3):= 1:
map(f, [$1..100]); # Robert Israel, Apr 15 2025
PROG
(Python)
from functools import cache
@cache
def a(n):
if n < 4: return int(n>1)
q, r = divmod(n, 4)
if r == 0: return 2*a(2*q) - a(q)
elif r == 1: return 2*a(2*q) + a(2*q+1)
elif r == 2: return 2*a(2*q+1) + a(2*q)
else: return 2*a(2*q+1) - a(q)
print([a(n) for n in range(1, 72)]) # Michael S. Branicky, Apr 15 2025
CROSSREFS
KEYWORD
nonn,look
AUTHOR
Jeffrey Shallit, Apr 15 2025
STATUS
approved
