cp's OEIS Frontend

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.

%I A250028 #22 Feb 28 2025 23:12:45
%S A250028 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,
%T A250028 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,
%U A250028 12,30,3,31,13,32,3,33,1,34,14,35,4,36,15,37,1,38,1
%N 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.
%C A250028 The least prime factor of n^2 + 1 is A089120(n).
%C A250028 a(2*j+1) = j+1 because 2 is the least prime factor of the even numbers.
%C A250028 a(n) = 1 if n is a term in A005574 (numbers n such that n^2 + 1 is prime).
%C A250028 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).
%C A250028 Property: if p = lpf(n^2 + 1), then p divides (n-p)^2 + 1.
%H A250028 Michel Lagneau, <a href="/A250028/b250028.txt">Table of n, a(n) for n = 1..10000</a>
%e A250028 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).
%e A250028 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).
%p A250028 with(numtheory):nn:=200:T:=array(1..nn):k:=0:
%p A250028 for m from 1 to nn do:
%p A250028 x:=factorset(m^2+1):n1:=nops(x):p:=x[1]:k:=k+1:T[k]:=p:
%p A250028 od:
%p A250028   for n from 1 to 150 do:
%p A250028   q:=T[n]:ii:=0:
%p A250028     for i from 1 to n do:
%p A250028       if T[i]=q then ii:=ii+1:
%p A250028       else
%p A250028       fi:
%p A250028     od:
%p A250028     printf(`%d, `, ii):
%p A250028   od:
%t A250028 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 *)
%o A250028 (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
%Y A250028 Cf. A002496, A005574, A089120, A242012.
%K A250028 nonn
%O A250028 1,3
%A A250028 _Michel Lagneau_, Nov 11 2014
%E A250028 Edited by _Jon E. Schoenfield_, Sep 11 2017