A059396 -id:A059396 - cp's OEIS frontend

A189172 Largest prime number tried when factoring n using trial division.

1, 1, 1, 2, 2, 2, 2, 2, 3, 2, 3, 2, 3, 2, 3, 2, 3, 3, 3, 2, 3, 3, 3, 2, 5, 3, 3, 2, 5, 3, 5, 2, 3, 3, 5, 3, 5, 3, 3, 2, 5, 3, 5, 3, 3, 3, 5, 2, 7, 5, 3, 3, 7, 3, 5, 2, 3, 5, 7, 3, 7, 5, 3, 2, 5, 3, 7, 3, 3, 5, 7, 3, 7, 5, 5, 3, 7, 3, 7, 2, 3, 5, 7, 3, 5, 5, 5, 3, 7, 3, 7, 3, 5, 5, 5, 2, 7, 7, 3, 5

Offset: 1

Dan Uznanski, May 02 2011

nonn

When factoring a number via trial division, one generally continues trying primes until it is certain that the remaining portion of n is prime. Sometimes, it is already clear that the remaining portion is prime before that portion is found; in this case, the last prime tried is the second to last prime factor.

			A(22) is 3, because after 3 is tried, it is clear that 11 is prime and no more factorization can be done.
A(18) is 3, because despite the largest prime factor (3) being obviously prime, it is not obviously the last factor until the first 3 is factored out.

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

Like A059396 but also works on composites; uses A006530, A087039, A000040.

prime(k), not shown, gives A000040[k].
function a(n) {
  var k = 1;
  while (Math.pow(prime(k),2) <= n) {
    var p = prime(k);
    if (n % p == 0) {
      n /= p;
    } else {
      k += 1;
    }
  }
  return p;
}

a[n_] := Module[{m = n, k = 1, p = 1, q}, While[q = Prime[k]; q^2 <= m, p = q; m = m/p^IntegerExponent[m, p]; k++]; p]; Array[a,100] (* T. D. Noe, May 04 2011 *)

a(n) = max(A087039(n), A007917(A000196(A006530(n)))).

A329403 Prime numbers p such that the sum of the prime numbers up to its square root equals primepi(p).

Original entry on oeis.org

11, 29, 59, 179, 389, 541, 5399, 12401, 13441, 40241, 81619, 219647, 439367, 1231547, 1263173, 1279021, 1699627, 1718471, 1756397, 1775903, 2603929, 2675927, 2699911, 2799149, 7580569, 7889627, 8206831, 18398983, 18470987, 34456153, 34660711, 34865977, 40564967, 40677407, 40787531

Offset: 1

Juan Moreno Borrallo, Nov 13 2019

nonn

There exist infinitely many such prime numbers, as proved by @GH from MO in the link provided to Mathoverflow. - Juan Moreno Borrallo, Mar 15 2021

It follows that the sum of prime numbers up to the square root of n is infinitely often equal to the prime counting function up to n. - Juan Moreno Borrallo, Mar 15 2021

			The square root of the 5th prime (11) is 3, and the sum of prime numbers up to 3 is 2+3 = 5, so 11 is a term of the sequence.

Juan Moreno Borrallo, An Approximation to the Prime Counting Function Through the Sum of Consecutive Prime Numbers, viXra:1710.0205, 2017.
Juan Moreno Borrallo, The prime counting function and the sum of prime numbers, viXra:1911.0316, 2019.
Mathoverflow, Set of prime numbers q such that the sum of the prime numbers p up to its square root equals primepi(q)

Cf. A000006, A007504, A059396.

[NthPrime(k):k in [1..100000]| &+PrimesInInterval(1, Floor(Sqrt(NthPrime(k)))) eq k]; // Marius A. Burtea, Nov 13 2019

Select[Prime@ Range@ PrimePi[10^6], Total@ Prime@ Range@ PrimePi@ Sqrt[#] == PrimePi@ # &] (* Michael De Vlieger, Dec 27 2019 *)

isok(p) = isprime(p) && (primepi(p) == sum(k=1, sqrtint(p), if (isprime(k), k))); \\ Michel Marcus, Nov 13 2019

cp's OEIS Frontend

A189172 Largest prime number tried when factoring n using trial division.

Views

Author

Keywords

Comments

Examples

Links

Crossrefs

Programs

JavaScript

Mathematica

Formula