A295609 -id:A295609 - cp's OEIS frontend

A295335 a(n) = least k >= 0 such that n OR k is prime (where OR denotes the bitwise OR operator).

2, 2, 0, 0, 1, 0, 1, 0, 3, 2, 1, 0, 1, 0, 17, 16, 1, 0, 1, 0, 3, 2, 1, 0, 5, 4, 5, 4, 1, 0, 1, 0, 5, 4, 9, 8, 1, 0, 9, 8, 1, 0, 1, 0, 3, 2, 1, 0, 5, 4, 9, 8, 1, 0, 73, 72, 3, 2, 1, 0, 1, 0, 65, 64, 3, 2, 1, 0, 3, 2, 1, 0, 1, 0, 5, 4, 3, 2, 1, 0, 3, 2, 1, 0, 43

Offset: 0

Rémy Sigrist, Nov 23 2017

See A295609 for the corresponding prime numbers.
We can show that this sequence is well defined by using Dirichlet's theorem on arithmetic progressions.
a(n) = 0 iff n is prime.
For any n >= 0, n AND a(n) = 0 (where AND denotes the bitwise AND operator).
If a(n) = x + y with x AND y = 0, then a(n + x) = y.
This sequence has similarities with A007920: here we check n OR k, there we check n + k.
See A295520 for the XOR variant.
For any k > 0, a(2^(6*k)-1) >= 2^(6*k) (hence the sequence is unbounded).

			For n = 42, 42 OR 0 = 42 is not prime, 42 OR 1 = 43 is prime, hence a(42) = 1.

Antti Karttunen, Table of n, a(n) for n = 0..8191
Antti Karttunen, Data supplement: n, a(n) computed for n = 0..65537
Rémy Sigrist, Scatterplot of the first 2^17 terms
Index entries for sequences related to binary expansion of n

Cf. A003986, A007920, A295520, A295609.

Table[Block[{k = 0}, While[! PrimeQ@ BitOr[k, n], k++]; k], {n, 0, 84}] (* Michael De Vlieger, Nov 26 2017 *)

avoid(n,i) = if (i, if (n%2, 2*avoid(n\2,i), 2*avoid(n\2,i\2)+(i%2)), 0) \\ (i+1)-th number k such that k AND n = 0
a(n) = for (i=0, oo, my (k=avoid(n,i)); if (isprime(n+k), return (k)))

For any k > 1, a(2*k+1) = a(2*k)-1.

A370730 a(n) is the least Fibonacci number f such that f AND n = n (where AND denotes the bitwise AND operator).

Original entry on oeis.org

0, 1, 2, 3, 5, 5, 55, 55, 8, 13, 987, 987, 13, 13, 17711, 17711, 21, 21, 55, 55, 21, 21, 55, 55, 89, 89, 987, 987, 1597, 1597, 1836311903, 1836311903, 34, 55, 34, 55, 55, 55, 55, 55, 233, 233, 17711, 17711, 1597, 1597, 17711, 17711, 55, 55, 55, 55, 55, 55, 55

Offset: 0

Rémy Sigrist, Feb 28 2024

This sequence is well defined:
- for any n >= 0, let w be such that n < 2^(w+1),
- the Fibonacci sequence mod 2^(w+1) is (3*2^w)-periodic,
- let p = 3*2^w,
- A000045(p) mod 2^(w+1) = A000045(0) mod 2^(w+1) = 0,
- A000045(p+1) mod 2^(w+1) = A000045(1) mod 2^(w+1) = 1,
- A000045(p-1) = A000045(p+1) - A000045(p), so A000045(p-1) mod 2^(w+1) = 1,
- A000045(p-2) = A000045(p) - A000045(p-1), so A000045(p-2) mod 2^(w+1) = -1,
- in other words, the binary expansion of A000045(p-2) ends with w+1 1's,
- and A000045(p-2) AND n = n, so a(n) <= A000045(p-2).

Paolo Xausa, Table of n, a(n) for n = 0..3800

Cf. A000045, A007283, A295609 (analog for prime numbers), A370731, A370744.

A370730[n_] := Block[{k = -1}, While[BitAnd[Fibonacci[++k], n] != n]; Fibonacci[k]]; Array[A370730, 100,0] (* Paolo Xausa, Mar 01 2024 *)

a(n) = { for (k = 0, oo, my (f = fibonacci(k)); if (bitand(f, n)==n, return (f););); }

a(n) >= n with equality iff n is a Fibonacci number.
a(n) = A000045(A370731(n)).
a(a(n)) = a(n).
a(A000045(k)) = A000045(k) for any k >= 0.

A370727 Lexicographically earliest sequence of distinct positive integers such that for any n > 0, prime(n) AND a(n) = a(n) (where prime(n) denotes the n-th prime number and AND denotes the bitwise AND operator).

Original entry on oeis.org

2, 1, 4, 3, 8, 5, 16, 17, 6, 9, 7, 32, 33, 10, 11, 20, 18, 12, 64, 65, 72, 13, 19, 24, 96, 36, 34, 35, 37, 48, 14, 128, 129, 130, 21, 22, 25, 131, 38, 40, 49, 52, 15, 192, 68, 66, 67, 23, 97, 69, 41, 39, 80, 26, 256, 257, 260, 258, 261, 264, 27, 288, 50, 51

Offset: 1

Rémy Sigrist, Feb 28 2024

In other words, the 1's in the binary expansion of the n-th term also appear in that of the n-th prime number.

This sequence is a permutation of the positive integers with inverse A370727: for any w > 0, there are infinitely many prime numbers whose binary expansions end with w 1's, and these are all occasions for an integer < 2^w to appear in the sequence.

			The first terms, alongside the corresponding binary expansions, are:
  n   a(n)  bin(a(n))  bin(prime(n))
  --  ----  ---------  -------------
   1     2         10             10
   2     1          1             11
   3     4        100            101
   4     3         11            111
   5     8       1000           1011
   6     5        101           1101
   7    16      10000          10001
   8    17      10001          10011
   9     6        110          10111
  10     9       1001          11101

Rémy Sigrist, Table of n, a(n) for n = 1..10000
Rémy Sigrist, PARI program
Index entries for sequences that are permutations of the natural numbers

Cf. A295609, A295989, A370728 (inverse).

PARI
```
See Links section.
```

A295642 Lexicographically earliest sequence of distinct prime numbers such that, for any n > 0, a(n) AND n = n (where AND denotes the binary AND operator).

Original entry on oeis.org

3, 2, 7, 5, 13, 23, 31, 11, 29, 43, 47, 61, 79, 127, 191, 17, 19, 59, 83, 53, 149, 151, 223, 89, 157, 251, 283, 317, 349, 383, 479, 37, 41, 103, 107, 101, 109, 167, 239, 173, 233, 367, 379, 431, 509, 751, 1087, 113, 179, 307, 311, 181, 373, 439, 503, 313, 443

Offset: 1

Rémy Sigrist, Nov 25 2017

This sequence is a permutation of the prime numbers (A000040) and for any prime p, a(n) = p for some n <= p.

For any n > 0, a(n) >= A295609(n).

			The first terms, alongside the binary representation of n and a(n), are:
  n   a(n)   bin(n)  bin(a(n))
  --  ----   ------  ---------
   1     3        1         11
   2     2       10         10
   3     7       11        111
   4     5      100        101
   5    13      101       1101
   6    23      110      10111
   7    31      111      11111
   8    11     1000       1011
   9    29     1001      11101
  10    43     1010     101011
  11    47     1011     101111
  12    61     1100     111101
  13    79     1101    1001111
  14   127     1110    1111111
  15   191     1111   10111111
  16    17    10000      10001
  17    19    10001      10011
  18    59    10010     111011
  19    83    10011    1010011
  20    53    10100     110101

Rémy Sigrist, Table of n, a(n) for n = 1..10000
Rémy Sigrist, Scatterplot of the first 2^17 terms
Rémy Sigrist, Colored scatterplot of the first 2^17 terms (where the color is function of A000120(n), the Hamming weight of n)
Rémy Sigrist, C++ program for A295642

Cf. A000040, A000120, A295609.

Fold[Append[#1, Block[{p = 2}, While[Nand[FreeQ[#1, p], BitAnd[p, #2] == #2], p = NextPrime@ p]; p]] &, {3}, Range[2, 57]] (* Michael De Vlieger, Nov 26 2017 *)

cp's OEIS Frontend

A295335 a(n) = least k >= 0 such that n OR k is prime (where OR denotes the bitwise OR operator).

Views

Author

Keywords

Comments

Examples

Links

Crossrefs

Programs

Mathematica

PARI

Formula

A370730 a(n) is the least Fibonacci number f such that f AND n = n (where AND denotes the bitwise AND operator).

Views

Author

Keywords

Comments

Links

Crossrefs

Programs

Mathematica

PARI

Formula

A370727 Lexicographically earliest sequence of distinct positive integers such that for any n > 0, prime(n) AND a(n) = a(n) (where prime(n) denotes the n-th prime number and AND denotes the bitwise AND operator).

Views

Author

Keywords

Comments

Examples

Links

Crossrefs

Programs

PARI

A295642 Lexicographically earliest sequence of distinct prime numbers such that, for any n > 0, a(n) AND n = n (where AND denotes the binary AND operator).

Views

Author

Keywords

Comments

Examples

Links

Crossrefs

Programs

Mathematica