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,3

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.

Links

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

Example

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).

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 *)

Prog

(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

Crossrefs

Cf. A002496, A005574, A089120, A242012.

Sequence in context: A130747 A370822 A055440 * A101279 A361735 A064576

Adjacent sequences: A250025 A250026 A250027 * A250029 A250030 A250031

Keyword

nonn

Author

Michel Lagneau, Nov 11 2014

Extensions

Edited by Jon E. Schoenfield, Sep 11 2017

Status

approved