A250028 a(n) is the number of positive integers k <= n such that lpf(k^2 + 1) = lpf(n^2 + 1), where lpf() is the least prime factor function.

1, 1, 2, 1, 3, 1, 4, 2, 5, 1, 6, 3, 7, 1, 8, 1, 9, 4, 10, 1, 11, 5, 12, 1, 13, 1, 14, 6, 15, 2, 16, 7, 17, 1, 18, 1, 19, 8, 20, 1, 21, 9, 22, 2, 23, 1, 24, 10, 25, 1, 26, 11, 27, 1, 28, 1, 29, 12, 30, 3, 31, 13, 32, 3, 33, 1, 34, 14, 35, 4, 36, 15, 37, 1, 38, 1

Offset: 1

Author

Michel Lagneau, Nov 11 2014

Keywords

• nonn

Comments

The least prime factor of n^2 + 1 is A089120(n).

a(2*j+1) = j+1 because 2 is the least prime factor of the even numbers.

a(n) = 1 if n is a term in A005574 (numbers n such that n^2 + 1 is prime).

a(n) = 1 if lpf(n^2 + 1) appears for the first time (example: a(50) = 1 because lpf(50^2 + 1) = lpf(41*61) = 41).

Property: if p = lpf(n^2 + 1), then p divides (n-p)^2 + 1.

Examples

			a(3) = 2 because the least prime factor of 3^2 + 1 is 2 and 2 is the 2nd positive integer k for which lpf(k^2 + 1) is 2 (the 1st occurrence is 1^2 + 1 = 2).
a(12) = 3 because the least prime factor of 12^2 + 1 = 5*29 is 5, and 5 is the 3rd occurrence (the 1st and 2nd are 2^2 + 1 = 5 and 8^2 + 1 = 5*13, respectively).
		

Links

• Michel Lagneau, Table of n, a(n) for n = 1..10000

Crossrefs

Cf. A002496, A005574, A089120, A242012.

Programs

Maple

with(numtheory):nn:=200:T:=array(1..nn):k:=0:
for m from 1 to nn do:
x:=factorset(m^2+1):n1:=nops(x):p:=x[1]:k:=k+1:T[k]:=p:
od:
  for n from 1 to 150 do:
  q:=T[n]:ii:=0:
    for i from 1 to n do:
      if T[i]=q then ii:=ii+1:
      else
      fi:
    od:
    printf(`%d, `, ii):
  od:

Mathematica

With[{s = Array[FactorInteger[#^2 + 1][[1, 1]] &, {76}]}, Reap[Do[Sow@ Count[Take[s, i], k_ /; k == FactorInteger[i^2 + 1][[1, 1]]], {i, Length@ s}]][[-1, 1]]] (* Michael De Vlieger, Sep 12 2017 *)

PARI

a(n) = my(gn = vecmin(factor(n^2+1)[,1])); sum(k=1, n, vecmin(factor(k^2+1)[,1]) == gn); \\ Michel Marcus, Sep 11 2017

Extensions

Edited by Jon E. Schoenfield, Sep 11 2017