A242012 -id:A242012 - 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.

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

Michel Lagneau, Nov 11 2014

nonn

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.

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

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

Cf. A002496, A005574, A089120, A242012.

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:

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

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

Edited by Jon E. Schoenfield, Sep 11 2017

A258840 a(n) is the least integer k such that there are n values of i <= k for which gpf(i^2 + 1) = gpf(k^2 + 1), where gpf(x) is the greatest prime factor of x.

Original entry on oeis.org

1, 3, 7, 38, 47, 157, 302, 327, 515, 616, 697, 798, 818, 1303, 2818, 3141, 3323, 5648, 6962, 9193, 9872, 13213, 13747, 15445, 16271, 17149, 18263, 20491, 20727, 24389, 26915, 29078, 31867, 37848, 38007, 40182, 41508, 43328, 46349, 55025, 62258, 63133, 66893

Offset: 1

Michel Lagneau, Jun 12 2015

nonn

A014442(n) gives the largest prime factor of n^2 + 1.
The primes of the sequence are 3, 7, 47, 157, 1303, 3323, 46349, ...
The corresponding sequence Gpf(a(n)^2+1) is 2, 5, 5, 17, 17, 29, 37, 37, 101, 101, 101, 101, 101, 101, 101, 101, 101, 97, 97, 97, 97, 401, 349, 389, 557, 557, 557, 557, 557, 421, 421, 421, 557, ... and it is interesting to observe the frequency of repetitions for the numbers 5, 17, 37, 97, 101, 557, ...

			a(3) = 7 because gpf(7^2 + 1) = gpf(3^2 + 1) = gpf(2^2 + 1) = 5 => 3 occurrences.
a(4) = 38 because gpf(38^2 + 1) = gpf(21^2 + 1) = gpf(13^2 + 1) = gpf(4^2 + 1) = 17 => 4 occurrences.

Cf. A014442, A242012.

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

gpf(n) = my(f=factor(n^2+1)); f[#f~,1];
nboc(k) = my(gpfk = gpf(k)); sum(i=1, k, gpf(i) == gpfk);
a(n) = my(k = 1); while (nbo(k) != n, k++); k; \\ Michel Marcus, Jun 12 2015

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.

Views

Author

Keywords

Comments

Examples

Links

Crossrefs

Programs

Maple

Mathematica

PARI

Extensions