A174090 Powers of 2 and odd primes; alternatively, numbers that cannot be written as a sum of at least three consecutive positive integers.

1, 2, 3, 4, 5, 7, 8, 11, 13, 16, 17, 19, 23, 29, 31, 32, 37, 41, 43, 47, 53, 59, 61, 64, 67, 71, 73, 79, 83, 89, 97, 101, 103, 107, 109, 113, 127, 128, 131, 137, 139, 149, 151, 157, 163, 167, 173, 179, 181, 191, 193, 197, 199, 211, 223, 227, 229, 233, 239, 241, 251, 256

Offset: 1

Author

Vladimir Joseph Stephan Orlovsky, Mar 07 2010, and Omar E. Pol, Feb 24 2014

Keywords

• nonn
• easy

Comments

From Omar E. Pol, Feb 24 2014: (Start)

Also the odd noncomposite numbers (A006005) and the powers of 2 with positive exponent, in increasing order.

If a(n) is composite and a(n) - a(n-1) = 1 then a(n-1) is a Mersenne prime (A000668), hence a(n-1)*a(n)/2 is a perfect number (A000396) and a(n-1)*a(n) equals the sum of divisors of a(n-1)*a(n)/2.

If a(n) is even and a(n+1) - a(n) = 1 then a(n+1) is a Fermat prime (A019434). (End)

Links

• Robert Israel, Table of n, a(n) for n = 1..10000
• Jaap Spies, A Bit of Math, The Art of Problem Solving, Jaap Spies Publishers (2019).
• Nieuw Archief voor Wiskunde, Problems/UWC, Problem C, Vol. 5/6, No. 2.

Crossrefs

Numbers not in A111774.

Equals A000079 UNION A065091.

Equals A067133 \ {6}.

Cf. A000040, A000203, A000396, A000668, A006005, A019434, A092506.

Cf. also A138591, A174069, A174070, A174071.

Programs

Maple

N:= 300: # to get all terms <= N
S:= {seq(2^i,i=0..ilog2(N))} union select(isprime,{ 2*i+1 $ i=1..floor((N-1)/2) }):
sort(convert(S,list)); # Robert Israel, Jun 18 2015

Mathematica

a[n_] := Product[GCD[2 i - 1, n], {i, 1, (n - 1)/2}] - 1;
Select[Range[242], a[#] == 0 &] (* Gerry Martens, Jun 15 2015 *)

PARI

list(lim)=Set(concat(concat(1,primes(lim)), vector(logint(lim\2,2),i,2^(i+1)))) \\ Charles R Greathouse IV, Sep 19 2024

PARI

select( {is_A174090(n)=isprime(n)||n==1<M. F. Hasler, Oct 24 2024

Python

from sympy import primepi
def A174090(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+x+(0 if x<=1 else 1-primepi(x))-x.bit_length())
    return bisection(f,n,n) # Chai Wah Wu, Sep 19 2024

Formula

a(n) ~ n log n. - Charles R Greathouse IV, Sep 19 2024

Extensions

This entry is the result of merging an old incorrect entry and a more recent correct version. N. J. A. Sloane, Dec 07 2015