cp's OEIS Frontend

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

%I A383066 #24 May 01 2025 18:53:08
%S A383066 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,
%T A383066 13,4,5,21,30,23,27,46,41,17,18,47,55,34,31,43,32,9,9,32,43,31,34,55,
%U A383066 47,18,17,41,46,27,23,30,21,5,6,31,47,38,47,83,76,33
%N A383066 A 2-regular sequence associated with the number of divisors of n^2 + 1 (A193432).
%C A383066 Shakov proves that the number of occurrences of k in this sequence is equal to the number of divisors of k^2+1.
%C A383066 It is a 2-regular sequence.
%H A383066 Rémy Sigrist, <a href="/A383066/b383066.txt">Table of n, a(n) for n = 1..8191</a>
%H A383066 Shreyansh Jaiswal, <a href="/A383066/a383066.png">Colored scatterplot of a(n) based on n modulo 4</a>
%H A383066 Anton Shakov, <a href="https://arxiv.org/abs/2405.03552">Polynomials in Z[x] whose divisors are enumerated by SL_2(N_0)</a>, arXiv:2405.03552 [math.NT], 2024.
%F A383066 a(n) obeys the recurrences:
%F A383066 a(4*n) = 2*a(2*n) - a(n)
%F A383066 a(4*n+1) = 2*a(2*n) + a(2*n+1)
%F A383066 a(4*n+2) = 2*a(2*n+1) + a(2*n)
%F A383066 a(4*n+3) = 2*a(2*n+1) - a(n)
%F A383066 and a(1) = 0, a(2) = 1, a(3) = 1.
%e A383066 For example, 7 occurs at indices 9, 14, 23, 24, 128, 255, and there are 6 divisors of 7^2+1 = 50.
%p A383066 f:= proc(n) option remember; local m,k;
%p A383066   m:= n mod 4;
%p A383066   k:= (n-m)/4;
%p A383066   if m = 0 then 2*procname(2*k) - procname(k)
%p A383066   elif m = 1 then 2*procname(2*k) + procname(2*k+1)
%p A383066   elif m = 2 then 2*procname(2*k+1)+procname(2*k)
%p A383066   else 2*procname(2*k+1)-procname(k)
%p A383066   fi;
%p A383066 end proc:
%p A383066 f(1):= 0: f(2):= 1: f(3):= 1:
%p A383066 map(f, [$1..100]); # _Robert Israel_, Apr 15 2025
%o A383066 (Python)
%o A383066 from functools import cache
%o A383066 @cache
%o A383066 def a(n):
%o A383066     if n < 4: return int(n>1)
%o A383066     q, r = divmod(n, 4)
%o A383066     if r == 0: return 2*a(2*q) - a(q)
%o A383066     elif r == 1: return 2*a(2*q) + a(2*q+1)
%o A383066     elif r == 2: return 2*a(2*q+1) + a(2*q)
%o A383066     else: return 2*a(2*q+1) - a(q)
%o A383066 print([a(n) for n in range(1, 72)]) # _Michael S. Branicky_, Apr 15 2025
%Y A383066 Cf. A193432.
%K A383066 nonn,look
%O A383066 1,4
%A A383066 _Jeffrey Shallit_, Apr 15 2025