A039634 Fixed point of "n -> n/2 or (n-1)/2 until result is prime".

1, 2, 3, 2, 5, 3, 7, 2, 2, 5, 11, 3, 13, 7, 7, 2, 17, 2, 19, 5, 5, 11, 23, 3, 3, 13, 13, 7, 29, 7, 31, 2, 2, 17, 17, 2, 37, 19, 19, 5, 41, 5, 43, 11, 11, 23, 47, 3, 3, 3, 3, 13, 53, 13, 13, 7, 7, 29, 59, 7, 61, 31, 31, 2, 2, 2, 67, 17, 17, 17, 71, 2, 73, 37, 37, 19, 19, 19, 79, 5, 5

Offset: 1

Author

Wouter Meeussen

Keywords

• nonn
• easy
• nice

Comments

a(n) is the largest prime whose binary expansion is an initial substring of n's binary expansion. - Charlie Neder, Oct 27 2018

a(1) = 1 by convention. - David A. Corneth, Oct 27 2018

Links

• Reinhard Zumkeller, Table of n, a(n) for n = 1..10000

Crossrefs

Cf. A039635-A039645, A010051, A039636, A039638, A039639.

Programs

Haskell

a039634 1 = 1
a039634 n = until ((== 1) . a010051) (flip div 2) n
-- Reinhard Zumkeller, Nov 17 2013

Mathematica

ner[ n_Integer ] := FixedPoint[ If[ EvenQ[ # ]&&#>2, #/2, If[ PrimeQ[ # ]||(#=== 1), #, (#-1)/2 ] ]&, n, 20 ]

PARI

a(n)=while(n>3 && !isprime(n), n\=2); n \\ Charles R Greathouse IV, Jun 23 2017

Python

from sympy import isprime
def a(n):
    while n>1 and not isprime(n): n>>=1
    return n
print([a(n) for n in range(1, 82)]) # Michael S. Branicky, Jul 24 2023

Extensions

Offset corrected by Reinhard Zumkeller, Nov 17 2013