A303077 a(1) = 1, and for n > 1, a(n) is the greatest prime number whose binary digits appear in order but not necessarily as consecutive digits in the binary representation of n.

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

Offset: 1

Author

Rémy Sigrist, Apr 18 2018

Keywords

• nonn
• base

Comments

This sequence has similarities with A078833; there binary digits have to be consecutive, here not.

For n > 1, a(n) is the greatest prime number appearing in the n-th row of A301983.

Examples

			The first terms, alongside the binary representations of n and of a(n), are:
  n   a(n)  bin(n)  bin(a(n))
  --  ----  ------  ---------
   1     1       1       1
   2     2      10      10
   3     3      11      11
   4     2     100     10_
   5     5     101     101
   6     3     110     11_
   7     7     111     111
   8     2    1000    10__
   9     5    1001    10_1
  10     5    1010    101_
  11    11    1011    1011
  12     3    1100    11__
  13    13    1101    1101
  14     7    1110    111_
  15     7    1111    111_
		

Links

• Rémy Sigrist, Table of n, a(n) for n = 1..10000
• Index entries for sequences related to binary expansion of n

Crossrefs

Cf. A078833, A301983.

Programs

PARI

a(n) = my (s=Set(1), b=binary(n)); for (i=2, #b, s=setunion(s, Set(apply(k->2*k+b[i], s)))); vecmax(select(k->k==1 || isprime(k), s))

Formula

a(2*n) = a(n) for any n > 1.

a(n) = n iff n is not composite.

a(n) = 2 iff n = 2^k for some k > 0.

a(n) >= A078833(n).