A383066 A 2-regular sequence associated with the number of divisors of n^2 + 1 (A193432).

0, 1, 1, 2, 3, 3, 2, 3, 7, 8, 5, 5, 8, 7, 3, 4, 13, 17, 12, 13, 21, 18, 7, 7, 18, 21, 13, 12, 17, 13, 4, 5, 21, 30, 23, 27, 46, 41, 17, 18, 47, 55, 34, 31, 43, 32, 9, 9, 32, 43, 31, 34, 55, 47, 18, 17, 41, 46, 27, 23, 30, 21, 5, 6, 31, 47, 38, 47, 83, 76, 33

Offset: 1

Author

Jeffrey Shallit, Apr 15 2025

Keywords

• nonn
• look

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.

Examples

			For example, 7 occurs at indices 9, 14, 23, 24, 128, 255, and there are 6 divisors of 7^2+1 = 50.
		

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.

Crossrefs

Cf. A193432.

Programs

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

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

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.