A089237 List of primes and squares.

0, 1, 2, 3, 4, 5, 7, 9, 11, 13, 16, 17, 19, 23, 25, 29, 31, 36, 37, 41, 43, 47, 49, 53, 59, 61, 64, 67, 71, 73, 79, 81, 83, 89, 97, 100, 101, 103, 107, 109, 113, 121, 127, 131, 137, 139, 144, 149, 151, 157, 163, 167, 169, 173, 179, 181, 191, 193, 196, 197, 199, 211, 223, 225, 227

Offset: 1

Author

N. J. A. Sloane, Dec 11 2003

Keywords

• nonn

Comments

Starting at a(1) = 1, this is the lexicographically earliest sequence of distinct numbers whose partial products are all exponentially odd numbers (A268335). - Amiram Eldar, Sep 24 2024

Links

• Zak Seidov, Table of n, a(n) for n = 1..1000

Crossrefs

Complement of A089229.

Cf. A000040, A000290, A010051, A010052, A161187, A161188, A268335.

Programs

Haskell

a089237 n = a089237_list !! (n-1)
a089237_list = merge a000040_list a000290_list where
   merge xs'@(x:xs) ys'@(y:ys) =
         if x < y then x : merge xs ys' else y : merge xs' ys
-- Reinhard Zumkeller, Dec 18 2012

Mathematica

m=100; Sort[Flatten[{Range[0,m]^2, Prime[Range[PrimePi[m^2]]]}]] (* Zak Seidov, Nov 05 2009 *)

PARI

is(n)=isprime(n) || issquare(n) \\ Charles R Greathouse IV, Oct 14 2016

PARI

{A89237=List([0..5]); A089237(n)=while(#A89237A340389. - M. F. Hasler, Jul 24 2021, edited Sep 01 2021

Python

from math import isqrt
from sympy import primepi
def A089237(n):
    def bisection(f,kmin=0,kmax=1):
        while f(kmax) > kmax: kmax <<= 1
        while kmax-kmin > 1:
            kmid = kmax+kmin>>1
            if f(kmid) <= kmid:
                kmax = kmid
            else:
                kmin = kmid
        return kmax
    def f(x): return int(n-1+x-primepi(x)-isqrt(x))
    return bisection(f,n-1,n-1) # Chai Wah Wu, Oct 12 2024

Formula

a(A161187(n)+1) = A000290(n); a(A161188(n)+1) = A000040(n). - Reinhard Zumkeller, Dec 18 2012

A010051(a(n)) + A010052(a(n)) = 1. - Reinhard Zumkeller, Jul 07 2014

a(n) ~ n log n. - Charles R Greathouse IV, Oct 14 2016