A193432 -id:A193432 - cp's OEIS frontend

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

Jeffrey Shallit, Apr 15 2025

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.

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

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.

Cf. A193432.

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

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

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.

A085722 Numbers k such that k^2 + 1 is a semiprime.

Original entry on oeis.org

3, 5, 8, 9, 11, 12, 15, 19, 22, 25, 28, 29, 30, 34, 35, 39, 42, 44, 45, 46, 48, 49, 50, 51, 52, 58, 59, 60, 61, 62, 64, 65, 69, 71, 76, 78, 79, 80, 85, 86, 88, 92, 95, 96, 100, 101, 102, 104, 106, 108, 114, 121, 131, 136, 139, 140, 141, 144, 145, 152, 154, 158, 159, 164

Offset: 1

Jason Earls, Jul 20 2003

Corresponding semiprimes k^2+1 are in A144255.

Solutions to the equation: A000005(1+k^2) = 4. - Enrique Pérez Herrero, May 03 2012

T. D. Noe, Table of n, a(n) for n = 1..1000

Cf. A014442, A089120, A144255, A193432.

lst={}; Do[If[Plus@@Last/@FactorInteger[n^2+1]==2, AppendTo[lst,n]], {n,0,200}]; lst (* Vladimir Joseph Stephan Orlovsky, Mar 24 2009 *)
Select[Range[200],PrimeOmega[#^2+1]==2&] (* Harvey P. Dale, Feb 28 2013 *)

select(vector(50,n,n),n->bigomega(n^2+1)==2)
\\ Zak Seidov, Feb 25 2011

A085722 = A193432^-1({2}). - M. F. Hasler, Mar 11 2012

A089120 Smallest prime factor of n^2 + 1.

Original entry on oeis.org

2, 5, 2, 17, 2, 37, 2, 5, 2, 101, 2, 5, 2, 197, 2, 257, 2, 5, 2, 401, 2, 5, 2, 577, 2, 677, 2, 5, 2, 17, 2, 5, 2, 13, 2, 1297, 2, 5, 2, 1601, 2, 5, 2, 13, 2, 29, 2, 5, 2, 41, 2, 5, 2, 2917, 2, 3137, 2, 5, 2, 13, 2, 5, 2, 17, 2, 4357, 2, 5, 2, 13, 2, 5, 2, 5477, 2, 53, 2, 5, 2, 37, 2, 5, 2

Offset: 1

Cino Hilliard, Dec 05 2003

This includes A002496, primes that are of the form n^2+1.

Note that a(n) is the smallest prime p such that n^(p+1) == -1 (mod p). - Thomas Ordowski, Nov 08 2019

H. Rademacher, Lectures on Elementary Number Theory, pp. 33-38.

Michael De Vlieger, Table of n, a(n) for n = 1..10000

Cf. A002496, A014442, A085722, A144255, A193432.

[Min(PrimeDivisors(n^2+1)):n in [1..100]]; // Marius A. Burtea, Nov 13 2019

Array[FactorInteger[#^2 + 1][[1, 1]] &, {83}] (* Michael De Vlieger, Sep 08 2015 *)

smallasqp1(m) = { for(a=1,m, y=a^2 + 1; f = factor(y); v = component(f,1); v1 = v[length(v)]; print1(v[1]",") ) }

A089120(n)=factor(n^2+1)[1,1]  \\ M. F. Hasler, Mar 11 2012

a(2k+1)=2; a(10k +/- 2)=5, else a(26k +/- 8)=13, else a(34k +/- 4)=17, else a(58k +/- 12)=29, else a(74k +/- 6)=37,... - M. F. Hasler, Mar 11 2012

A089120(n) = 2 if n is odd, else A089120(n) = min { A002144(k) | n = +/- A209874(k) (mod 2*A002144(k)) }.

A144255 Semiprimes of the form k^2+1.

Original entry on oeis.org

10, 26, 65, 82, 122, 145, 226, 362, 485, 626, 785, 842, 901, 1157, 1226, 1522, 1765, 1937, 2026, 2117, 2305, 2402, 2501, 2602, 2705, 3365, 3482, 3601, 3722, 3845, 4097, 4226, 4762, 5042, 5777, 6085, 6242, 6401, 7226, 7397, 7745, 8465, 9026, 9217, 10001, 10202

Offset: 1

T. D. Noe, Sep 16 2008

Iwaniec proves that there are an infinite number of semiprimes or primes of the form n^2+1. Because n^2+1 is not a square for n>0, all such semiprimes have two distinct prime factors.

Moreover, this implies that one prime factor p of n^2+1 is strictly smaller than n, and therefore also divisor of (the usually much smaller) m^2+1, where m = n % p (binary "mod" operation). - M. F. Hasler, Mar 11 2012

Charles R Greathouse IV, Table of n, a(n) for n = 1..10000
Henryk Iwaniec, Almost-primes represented by quadratic polynomials, Inventiones Mathematicae 47 (2) (1978), pp. 171-188.

Cf. A001358, A085722, A069987, A193432.

Subsequence of A134406.

IsSemiprime:= func; [s: n in [1..100] | IsSemiprime(s) where s is n^2 + 1]; // Vincenzo Librandi, Sep 22 2012

Select[Table[n^2  + 1, {n, 100}], PrimeOmega[#] == 2&] (* Vincenzo Librandi, Sep 22 2012 *)

select(n->bigomega(n)==2,vector(500,n,n^2+1)) \\ Zak Seidov Feb 24 2011

from sympy import primeomega
from itertools import count, takewhile
def aupto(limit):
    form = takewhile(lambda x: x <= limit, (k**2+1 for k in count(1)))
    return [number for number in form if primeomega(number)==2]
print(aupto(10202)) # Michael S. Branicky, Oct 26 2021

a(n) = A085722(n)^2 + 1.

Equals { n^2+1 | A193432(n)=2 }. - M. F. Hasler, Mar 11 2012

A209874 Least m > 0 such that the prime p=A002313(n+1) divides m^2+1.

Original entry on oeis.org

1, 2, 8, 4, 12, 6, 32, 30, 50, 46, 34, 22, 10, 76, 98, 100, 44, 28, 80, 162, 112, 14, 122, 144, 64, 16, 82, 60, 228, 138, 288, 114, 148, 136, 42, 104, 274, 334, 20, 266, 392, 254, 382, 348, 48, 208, 286, 52, 118, 86, 24, 516, 476, 578, 194, 154, 504, 106, 58, 26, 566, 96, 380, 670, 722, 62, 456, 582, 318, 526, 246, 520, 650, 726, 494, 324

Offset: 0

M. F. Hasler, Mar 11 2012

nonn

This yields the prime factors of numbers of the form N^2+1, cf. formula in A089120: For n=0,1,2,... check whether N = +/- a(n) [mod 2*A002313(n+1)], if so, then A002313(n+1) is a prime factor of N^2+1.
Obviously, p then divides (2kp +/- a(n))^2+1 for all k >=0 ; in particular it will be the least prime factor of such numbers if there is no earlier match.
Alternatively one could deal separately with the case of odd N, for which p=2 divides N^2+1, and even N, for which only Pythagorean primes A002144(n)=A002313(n+1) can be prime factors of N^2+1.

Cf. A002496, A014442, A085722, A144255, A089120, A193432.

Cf. A002314, A177979.

A209874(n)=if( n, 2*lift(sqrt(Mod(-1, A002144[n])/4)), 1)

/* for illustrative purpose: a(n) is the smaller of the 2 possible remainders mod 2*p of numbers N such that N^2+1 has p as smallest prime factor */ forprime( p=1,199, p>2 & p%4 != 1 & next; my(c=[]); for(i=1,9e9, factor(i^2+1)[1,1]==p |next; c=vecsort(concat(c,i%(2*p)),,8); #c==1 || print1(","c[1]) || break))

For n>0, A209874(n) = 2*sqrt(-1/4 mod A002144(n)), where sqrt(a mod p) stands for the positive x < p/2 such that x^2=a in Z/pZ.

A209874(n) = A209877(n)*2 for n>0.

A193433 Sum of the divisors of n^2+1.

Original entry on oeis.org

1, 3, 6, 18, 18, 42, 38, 93, 84, 126, 102, 186, 180, 324, 198, 342, 258, 540, 434, 546, 402, 756, 588, 972, 578, 942, 678, 1332, 948, 1266, 972, 1596, 1302, 1980, 1260, 1842, 1298, 2484, 1842, 2286, 1602, 2613, 2124, 3534, 2100, 3042, 2220, 4536, 2772, 3606

Offset: 0

Michel Lagneau, Jul 28 2011

nonn

			a(7) = 93 because 7^2+1 = 50 and the sum of the 6 divisors { 1, 2, 5, 10, 25, 50} is 93.

Amiram Eldar, Table of n, a(n) for n = 0..10000

Cf. A000203, A002522, A193432.

with(numtheory):for n from 0 to 110 do:x:=divisors(n^2+1):n1:=nops(x):s:=0:for m from 1 to n1 do: s:=s+x[m]:od: printf(`%d, `, s):od:

Table[Total[Divisors[n^2 + 1]], {n, 0, 100}] (* T. D. Noe, Jul 28 2011 *)
DivisorSigma[1,Range[0,50]^2+1] (* Harvey P. Dale, Aug 03 2020 *)

a(n) = sigma(n^2+1); \\ Michel Marcus, Mar 17 2018

from sympy import divisor_sigma
def A193433(n): return divisor_sigma(n**2+1) # Chai Wah Wu, Apr 17 2025

a(n) = A000203(A002522(n)). - Michel Marcus, Mar 16 2018

A193583 Number of fixed points under iteration of sum of squares of digits in base b.

Original entry on oeis.org

1, 3, 1, 3, 1, 5, 3, 3, 1, 3, 3, 7, 1, 3, 1, 7, 5, 3, 1, 7, 3, 7, 1, 3, 1, 7, 3, 3, 3, 7, 5, 7, 3, 3, 1, 7, 5, 3, 1, 5, 3, 11, 3, 3, 3, 15, 3, 3, 3, 3, 3, 7, 1, 7, 1, 15, 3, 3, 3, 3, 3, 7, 3, 3, 1, 7, 7, 3, 5, 3, 7, 15, 1, 7, 3, 7, 3, 3, 3, 7, 5, 15, 1, 3, 3

Offset: 2

Martin Renner, Jul 31 2011

If b>=2 and a>=b^2 then S(a,2,b)

From Christian N. K. Anderson, Apr 22 2013: (Start)

It can be shown that no fixed point has more than 2 digits in base b, and that the two-digit number A+Bb must satisfy the condition that (2A-1)^2+(2B-b)^2=1+b^2. The number of ways of writing (1+b^2) as the sum of two squares is d(1+b^2)-1, where d(n) is the number of divisors of n. (Beardon, 1998, Theorem 3.1)

From the above chain of logic follows:

- The value of the fixed points can be determined by investigating only 8*A002654(n^2+1) pairs of possibilities.

- a(n) = A000005(n^2+1)-1

- a(n) = A193432(n)-1

a(n)=1 iff n^2+1 is prime, and the value of that single fixed point is 1.

The only odd value of n for which a(n)=9 is n=239.

Several values of a(n) occur very infrequently. For example, a(1068)=13 is the only occurrence of 13 for n < 10000. (End)

			In the decimal system all integers go to (1) or (4, 16, 37, 58, 89, 145, 42, 20) under the iteration of sum of squares of digits, hence there is one fixed point and one cycle. Therefore a(10) = 1.
a(5)=3 because 1 is always a fixed point; also in base 5, decimal 13 -> 23 and 2^2+3^2 = 13; decimal 18 -> 33 and 3^2+3^2 = 18. - _Christian N. K. Anderson_, Apr 22 2013

Martin Renner and Christian N. K. Anderson, Table of n, a(n) for n = 2..10000 (first 299 values from Martin Renner)
Alan F. Beardon, Sums of Squares of Digits, The Mathematical Gazette, 82(1998), 379-388.
H. G. Grundman, E. A. Teeple, Generalized Happy Numbers, Fibonacci Quarterly 39 (2001), nr. 5, p. 462-466.

Equals A193432-1.
Cf. A007770.
Cf. A002654, A000005.

library(gmp); y=rep(0,10000)
for(B in 1:10000) y[B]=prod(table(as.numeric(factorize(1+as.bigz(B)^2)))+1)-1; y # Christian N. K. Anderson, Apr 22 2013

A193462 Sum of the distinct prime divisors of n^2+1.

Original entry on oeis.org

0, 2, 5, 7, 17, 15, 37, 7, 18, 43, 101, 63, 34, 24, 197, 115, 257, 36, 18, 183, 401, 32, 102, 60, 577, 315, 677, 80, 162, 423, 70, 52, 46, 116, 102, 615, 1297, 144, 22, 763, 1601, 31, 358, 44, 162, 1015, 102, 37, 466, 1203, 102, 1303, 546, 288, 2917, 108, 3137

Offset: 0

Michel Lagneau, Jul 28 2011

nonn

			a(7) = 7 because 7^2+1 = 2*5^2 and the sum of the 2 distinct prime divisors {2, 5} is 7.

Harvey P. Dale, Table of n, a(n) for n = 0..1000

Cf. A193432, A193433.

with(numtheory):for n from 0 to 110 do:x:=factorset(n^2+1):n1:=nops(x):s:=0:for m from 1 to n1 do: s:=s+x[m]:od: printf(`%d, `, s):od:

Join[{0},Table[Total[Transpose[FactorInteger[n^2+1]][[1]]],{n,60}]] (* Harvey P. Dale, Oct 18 2013 *)

A069062 Numbers k such that k^2-1 and k^2+1 have the same number of positive divisors.

Original entry on oeis.org

2, 3, 12, 30, 42, 60, 68, 102, 108, 112, 123, 128, 162, 168, 198, 200, 212, 213, 252, 294, 302, 312, 318, 333, 336, 338, 372, 387, 447, 448, 450, 462, 498, 502, 522, 542, 578, 592, 598, 600, 606, 612, 648, 672, 678, 708, 717, 752, 762, 795, 808, 810, 812

Offset: 1

Benoit Cloitre, Apr 04 2002

Amiram Eldar, Table of n, a(n) for n = 1..10000

Cf. A000005, A002522, A005563, A193432, A347191.

Select[Range[1000], DivisorSigma[0, #^2 - 1] == DivisorSigma[0, #^2 + 1] &] (* Amiram Eldar, Jun 04 2022 *)

isok(n) = numdiv(n^2-1) == numdiv(n^2+1); \\ Michel Marcus, Nov 24 2013

A333169 a(n) = phi(n^2 + 1), where phi is the Euler totient function (A000010).

Original entry on oeis.org

1, 1, 4, 4, 16, 12, 36, 20, 48, 40, 100, 60, 112, 64, 196, 112, 256, 112, 240, 180, 400, 192, 384, 208, 576, 312, 676, 288, 624, 420, 832, 432, 800, 432, 1056, 612, 1296, 544, 1088, 760, 1600, 812, 1408, 720, 1776, 1012, 2016, 768, 1840, 1200, 2400, 1300, 2160

Offset: 0

Amiram Eldar, Mar 09 2020

nonn

			a(0) = phi(0^2 + 1) = phi(1) = 1.

Steven R. Finch, Mathematical Constants II, Encyclopedia of Mathematics and Its Applications, Cambridge University Press, Cambridge, 2018, p. 166.

Amiram Eldar, Table of n, a(n) for n = 0..10000

Cf. A000010, A002522, A067720, A193432, A193433, A333167.

Mathematica
```
Table[EulerPhi[k^2 + 1], {k, 0, 100}]
```

a(n) = eulerphi(n^2+1); \\ Michel Marcus, Mar 10 2020

a(n) = A000010(A002522(n)).

Showing 1-10 of 26 results. Next

cp's OEIS Frontend

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

Views

Author

Keywords

Comments

Examples

Links

Crossrefs

Programs

Maple

Python

Formula

A085722 Numbers k such that k^2 + 1 is a semiprime.

Views

Author

Keywords

Comments

Links

Crossrefs

Programs

Mathematica

PARI

Formula

A089120 Smallest prime factor of n^2 + 1.

Views

Author

Keywords

Comments

References

Links

Crossrefs

Programs

Magma

Mathematica

PARI

PARI

Formula

A144255 Semiprimes of the form k^2+1.

Views

Author

Keywords

Comments

Links

Crossrefs

Programs

Magma

Mathematica

PARI

Python

Formula

A209874 Least m > 0 such that the prime p=A002313(n+1) divides m^2+1.

Views

Author

Keywords

Comments

Crossrefs

Programs

PARI

PARI

Formula

A193433 Sum of the divisors of n^2+1.

Views

Author

Keywords

Examples

Links

Crossrefs

Programs

Maple

Mathematica

PARI

Python

Formula

A193583 Number of fixed points under iteration of sum of squares of digits in base b.

Views

Author

Keywords

Comments

Examples