A122155 -id:A122155 - cp's OEIS frontend

A122198 Permutation of natural numbers: a recursed variant of A122155.

0, 1, 2, 3, 4, 7, 6, 5, 8, 15, 14, 13, 12, 9, 10, 11, 16, 31, 30, 29, 28, 25, 26, 27, 24, 17, 18, 19, 20, 23, 22, 21, 32, 63, 62, 61, 60, 57, 58, 59, 56, 49, 50, 51, 52, 55, 54, 53, 48, 33, 34, 35, 36, 39, 38, 37, 40, 47, 46, 45, 44, 41, 42, 43, 64, 127, 126, 125, 124, 121

Offset: 0

Antti Karttunen, Aug 25 2006

nonn

Maps between A096115 and A096111.

Index entries for sequences that are permutations of the natural numbers

Inverse: A122199.

(define (A122198 n) (if (< n 1) n (A122155 (+ (A053644 n) (A122198 (A053645 n))))))

a(0)=0, otherwise a(n) = A122155(A053644(n)+a(A053645(n))).

A122199 Permutation of natural numbers: a recursed variant of A122155.

Original entry on oeis.org

0, 1, 2, 3, 4, 7, 6, 5, 8, 13, 14, 15, 12, 11, 10, 9, 16, 25, 26, 27, 28, 31, 30, 29, 24, 21, 22, 23, 20, 19, 18, 17, 32, 49, 50, 51, 52, 55, 54, 53, 56, 61, 62, 63, 60, 59, 58, 57, 48, 41, 42, 43, 44, 47, 46, 45, 40, 37, 38, 39, 36, 35, 34, 33, 64, 97, 98, 99, 100, 103, 102

Offset: 0

Antti Karttunen, Aug 25 2006

nonn

Maps between A096111 and A096115.

Index entries for sequences that are permutations of the natural numbers

Inverse: A122198.

Cf. A053644, A053645, A096111, A096115, A122155.

(define (A122199 n) (if (< n 1) n (let ((m (A122155 n))) (+ (A053644 m) (A122199 (A053645 m))))))

a(0)=0, otherwise a(n) = A053644(A122155(n)) + a(A053645(A122155(n))).

A381839 In the binary expansion of n (without leading zeros): complement the bits strictly between the leftmost and the rightmost 0's, if any.

Original entry on oeis.org

0, 1, 2, 3, 4, 5, 6, 7, 10, 9, 8, 11, 12, 13, 14, 15, 22, 21, 20, 19, 18, 17, 16, 23, 26, 25, 24, 27, 28, 29, 30, 31, 46, 45, 44, 43, 42, 41, 40, 39, 38, 37, 36, 35, 34, 33, 32, 47, 54, 53, 52, 51, 50, 49, 48, 55, 58, 57, 56, 59, 60, 61, 62, 63, 94, 93, 92, 91

Offset: 0

Rémy Sigrist, Mar 08 2025

This sequence is a self-inverse permutation of the nonnegative integers.
This sequence has similarities with A122155 (where we complement bits between the leftmost and the rightmost 1's).
This sequence has infinitely many fixed points: A000225, A030130, and the positive numbers whose binary expansion have exactly two 0's that are also adjacent to each other.

			The first terms, in decimal and in binary, are:
  n   a(n)  bin(n)  bin(a(n))
  --  ----  ------  ---------
   0     0       0          0
   1     1       1          1
   2     2      10         10
   3     3      11         11
   4     4     100        100
   5     5     101        101
   6     6     110        110
   7     7     111        111
   8    10    1000       1010
   9     9    1001       1001
  10     8    1010       1000
  11    11    1011       1011
  12    12    1100       1100
  13    13    1101       1101
  14    14    1110       1110
  15    15    1111       1111
  16    22   10000      10110

Cf. A000225, A030130, A122155, A381852.

a(n) = { my (b = binary(n)); for (i = 1, #b, if (b[i]==0, forstep (j = #b, 1, -1, if (b[j]==0, for (k = i+1, j-1, b[k] = 1-b[k];); return (fromdigits(b, 2)););););); return (n); }

def a(n):
    b = bin(n)[2:]
    zl, zr = b.find('0'), b.rfind('0')
    return n if abs(zl-zr) < 2 else int(b[:zl+1]+"".join('0' if bi == '1' else '1' for bi in b[zl+1:zr])+b[zr:], 2)
print([a(n) for n in range(70)]) # Michael S. Branicky, Mar 09 2025

def A381839(n): return n^((1<1 else n # Chai Wah Wu, Mar 09 2025

a(2*n + 1) = 2*a(n) + 1.

A359416 Write n as 2^m - k, where 2^m is the least power of 2 >= n (0 <= k <= 2^(m-1)-1). For n a power of 2 (k = 0), a(n) = n. For numbers with k > 0, a(n) is the least p*a(k) which has not occurred previously, the count of k being taken from right to left (backwards) from k = 1 at 2^m - 1.

Original entry on oeis.org

1, 2, 3, 4, 9, 6, 5, 8, 25, 18, 27, 12, 15, 10, 7, 16, 49, 50, 105, 36, 81, 54, 75, 24, 35, 30, 45, 20, 21, 14, 11, 32, 121, 98, 231, 100, 495, 210, 175, 72, 225, 162, 243, 108, 315, 150, 147, 48, 77, 70, 165, 60, 135, 90, 125, 40, 55, 42, 63, 28, 33, 22, 13, 64

Offset: 1

David James Sycamore, Dec 30 2022

nonn

A variant of the recursive definition of the Doudna sequence A005940, and A356886. Whereas a sequence is normally computed in natural order (A000027) of its indices (a(1), a(2), a(3), etc.), in this case terms with indices n other than powers of 2 are computed backwards, right to left from the least power of 2 exceeding n (ordering as in A122155). For example, with terms between a(4) and a(8) the order of computation is a(7), then a(6), then a(5), each time choosing a least novel number matching the definition, see Example. Compare with similar sequence A356886, where a similar definition is used but the count is conventional: left to right.

Conjectured to be a permutation of the positive integers in which primes appear in natural order. The even bisection, when divided by 2, reproduces the sequence.

			a(3) = 3 because 3 = 2^2 - 1, so k = 1 and 3 is the least odd prime multiple of a(1).
a(7) = 5 because 7 = 2^3 - 1, k = 1, a(1) = 1 and 5 is the least multiple of 1 not seen already. (At this point a(5), a(6) have not been found.)
a(6) = 6 since k = 2, a(2) = 2, and 3*2 is the least number not seen already.
a(5) = 9 since k = 3, a(3) = 3, so we choose 3*3.

Michael De Vlieger, Table of n, a(n) for n = 1..16384
Michael De Vlieger, Log log scatterplot of a(n), n = 1..2^12.
Michael De Vlieger, Labeled fan-style binary tree showing a(n), n = 1..2^12 in levels k such that n = 2^k+1..2^(k+1), with a color function indicating a(2^k) and a(n), where a(n) = a(2^k) in green, a(n) < a(2^k) in blues, and a(n) > a(2^k) in yellows, oranges, and reds.

Cf. A000027, A005940, A122155, A356886, A357057.

nn = 2^6; c[] = False; Do[Set[{m, k}, {2, n - 2^Floor[Log2[n]]}]; If[k == 0, Set[{a[n], c[n]}, {n, True}], While[Set[t, Prime[m] a[k]]; c[t], m++]; Set[{a[2^#/(1 + Boole[IntegerQ[Log2[n]]]) - n + 2^(# - 1) &@ IntegerLength[n, 2]], c[t]}, {t, True}]], {n, 2^Ceiling[Log2[nn]] }]; Array[a, nn] (* _Michael De Vlieger, Jan 02 2023 *)

a(2*n)/2 = a(n); n >= 1.
a(2^n - 1) = prime(n); n >= 2.
a(2^n + 1) = prime(n)^2; n >= 2.
At the occurrence of 2^n (n >= 3) the following pattern of five successive terms is observed: 3*prime(n-1), 2*prime(n-1), prime(n), 2^n, prime(n)^2, ....
For n >= 2, a(2^n + 1)/a(2^n - 1) = prime(n); compare with A357057).

A071911 Numbers m such that Stern's diatomic A002487(m) is divisible by 3.

Original entry on oeis.org

0, 5, 7, 10, 14, 20, 28, 33, 35, 40, 45, 47, 49, 51, 56, 61, 63, 66, 70, 73, 75, 80, 85, 87, 90, 94, 98, 102, 105, 107, 112, 117, 119, 122, 126, 132, 140, 146, 150, 153, 155, 160, 165, 167, 170, 174, 180, 188, 196, 204, 210, 214, 217, 219, 224, 229, 231, 234, 238, 244, 252

Offset: 0

N. J. A. Sloane, Jun 13 2002

nonn

From Kevin Ryde, Jan 09 2021: (Start)
Dijkstra gives bit pattern {0}1{?0{1}0|?1{0}1}?1{0} for the terms of this sequence, where | is alternative, {x} is zero or more of x, and ? is a single 0 or 1.  Dijkstra formed this from a finite state automaton (states as pairs of Stern diatomic values mod 3 = A071412).  The minimized automaton is as follows.  State A is the start and the sole accepting state.
                 +---+
        1 +----> | B | <-----+ 0
          |      +---+       |
  0 +-- +===+      |       +---+ --+ 1
    +-> | A |      |0,1    | D | <-+
  start +===+      v       +---+
          ^      +---+       ^
        1 +----- | C | ------+ 0
                 +---+
a(n) can be calculated from n by a usual unranking in this automaton, using the number of strings of a given length k accepted from each state.  Reznick's A122946(k) is the number of strings accepted starting from B.  A089977(k-1) is the number accepted starting from C.
Dijkstra shows that for any m, a bit reversal (A030101) or an internal bit complement (A122155) of m are no change to the resulting Diatomic(m) value.  So here if m is a term then so are A030101(m) and A122155(m).  In the bit pattern, a reversal or complement between (but not including) the outermost 1's is no change.
(End)

Edsger W. Dijkstra, An exercise for Dr. R. M. Burstall, 1976. Reprinted in Edsger W. Dijkstra, Selected Writings on Computing, Springer-Verlag, 1982, pages 215-216.
Edsger W. Dijkstra, More about the function ``fusc'', 1976. Reprinted in Edsger W. Dijkstra, Selected Writings on Computing, Springer-Verlag, 1982, pages 230-232.
Bruce Reznick, Regularity Properties of the Stern Enumeration of the Rationals, Journal of Integer Sequences, volume 11, 2008, article 08.4.1. Also arXiv:math/0610601 [math.NT] 2006, and author's copy. Section 5 theorem 18 onward.

Cf. A071412 (diatomic mod 3), A122946 (count by bit length), A089977 (half that).

{ my(M=Mod('x, 'x^2+'x+2),
            f=[2,1, 0,-'x-1, -2,1, 0,'x-1],
            table=[1,3, 5,5, 7,1, 3,7]);
a(n) = n<<=2; my(k=if(n,logint(n,2)+1), p=M^k, s=1);
  while(k>=0,
    my(t = n + (3<>2; }  \\ Kevin Ryde, Jan 09 2021

def aupto(nn):
  ok = [1] + [0 for i in range(nn)]
  for m in range(nn+1):
    if ok[m]:  # from formula
      for i in [2*m, 8*m-5, 8*m+5, 8*m-7, 8*m+7]:
        if 0 <= i <= nn: ok[i] = 1
  return [m for m in range(nn+1) if ok[m]]
print(aupto(252)) # Michael S. Branicky, Jan 09 2021

from itertools import count, islice
from functools import reduce
def inA071911(n): return not (n and sum(reduce(lambda x,y:(x[0],(x[0]+x[1])%3) if int(y) else ((x[0]+x[1])%3,x[1]),bin(n)[-1:2:-1],(1,0)))%3)
def A071911_gen(startvalue=0): # generator of terms >= startvalue
    return filter(inA071911, count(max(startvalue,0)))
A071911_list = list(islice(A071911_gen(),20)) # Chai Wah Wu, May 18 2023

If m is in the sequence, then 2*m, 8*m +- 5, and 8*m +- 7 (when nonnegative) are in the sequence. Starting from m=0, this rule generates the sequence. [Reznick section 5 theorem 18] - Kevin Ryde, Jan 09 2021

cp's OEIS Frontend

A122198 Permutation of natural numbers: a recursed variant of A122155.

Views

Author

Keywords

Comments

Links

Crossrefs

Programs

Scheme

Formula

A122199 Permutation of natural numbers: a recursed variant of A122155.

Views

Author

Keywords

Comments

Links

Crossrefs

Programs

Scheme

Formula

A381839 In the binary expansion of n (without leading zeros): complement the bits strictly between the leftmost and the rightmost 0's, if any.

Views

Author

Keywords

Comments

Examples

Links

Crossrefs

Programs

PARI

Python

Python

Formula

A359416 Write n as 2^m - k, where 2^m is the least power of 2 >= n (0 <= k <= 2^(m-1)-1). For n a power of 2 (k = 0), a(n) = n. For numbers with k > 0, a(n) is the least p*a(k) which has not occurred previously, the count of k being taken from right to left (backwards) from k = 1 at 2^m - 1.

Views

Author

Keywords

Comments

Examples

Links

Crossrefs

Programs

Mathematica

Formula

A071911 Numbers m such that Stern's diatomic A002487(m) is divisible by 3.

Views

Author

Keywords

Comments

Links

Crossrefs

Programs

PARI

Python

Python

Formula