cp's OEIS Frontend

This is a front-end for the Online Encyclopedia of Integer Sequences, made by Christian Perfect. The idea is to provide OEIS entries in non-ancient HTML, and then to think about how they're presented visually. The source code is on GitHub.

Showing 1-3 of 3 results.

A225589 Inverse of permutation in A217122.

Original entry on oeis.org

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

Views

Author

Reinhard Zumkeller, May 11 2013

Keywords

Links

Programs

  • Haskell
    import Data.List (elemIndex)
import Data.Maybe (fromJust)
a225589 = (+ 1) . fromJust . (`elemIndex` a217122_list)

A075311 a(1) = 1; for n > 1, a(n) is the smallest number m > a(n-1) such that the number of 1's in the binary expansion of m is not already in the sequence.

Original entry on oeis.org

1, 3, 5, 6, 9, 10, 12, 15, 17, 18, 20, 23, 24, 27, 29, 30, 33, 34, 36, 39, 40, 43, 45, 46, 48, 51, 53, 54, 57, 58, 60, 65, 66, 68, 71, 72, 75, 77, 78, 80, 83, 85, 86, 89, 90, 92, 96, 99, 101, 102, 105, 106, 108, 113, 114, 116, 120, 127, 129, 130, 132, 135, 136, 139, 141
Offset: 1

Views

Author

Phil Carmody, Oct 11 2002

Keywords

Comments

If A000120(k) is in the sequence then k is not.
Differs from A001969: 63 is not included since it has 6 bits set.

Examples

			We start with a(1)=1. Then 2 is not included since it has one bit set and 1 is in the sequence. Next, 3 is included since it has 2 one bits and 2 is not in the sequence. And so on.

Links

Crossrefs

Cf. A000120, A001969.
Cf. A075517, A217122.

Programs

  • Haskell
    a075311 n = a075311_list !! (n-1)
a075311_list = 1 : f 2 [1] where
   f x ys = if a000120 x `elem` ys then f (x + 1) ys
                                   else x : f (x + 1) (x : ys)
-- Reinhard Zumkeller, Apr 22 2012
  • PARI
    v=vector(1000): v[1]=1: for(curr=2,1000,e=A000120(curr): if(v[e],continue,v[curr]=1)): for(k=1,1000,if(v[k],print1(k",")))

Extensions

Edited by Ralf Stephan, Sep 14 2003

A357961 a(1) = 1, and for any n > 0, a(n+1) is the k-th positive number not yet in the sequence, where k is the Hamming weight of a(n).

Original entry on oeis.org

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

Views

Author

Rémy Sigrist, Oct 22 2022

Keywords

Comments

This sequence is a permutation of the positive integers:
- Let e = A000523 and w = A000120.
- Lemma: a(n) <= n + e(n)
- This property is true for n = 1.
- Assume that a(n) <= n + e(n) for some n >= 1.
- Then a(n+1) <= n + w(a(n))
<= n + e(a(n))
<= n + e(n + e(n))
<= n + e(2*n)
<= n + 1 + e(n)
<= n + 1 + e(n + 1) - QED.
- If this sequence is not a permutation, then some number is missing.
- Let v be the least number that does not appear in the sequence.
- At some point, v is the least number not yet in the sequence.
- From now on, powers of 2 can no longer appear in the sequence.
- So there are infinitely many numbers that do not appear in the sequence.
- Let w be the least number > v that does not appear in the sequence.
- At some point, v and w are the two least numbers not yet in the sequence.
- Say this happens after m terms and max(a(1), ..., a(m)) < 2^k (with k > 0).
- From now on, powers of 2 and sums of two powers of 2 can no longer appear.
- So the numbers 2^k, 2^k + 2^i where i = 0..k-1 won't appear,
and the numbers 2^(k+1), 2^(k+1) + 2^i where i = 0..k won't appear.
- So among the first 2^(k+2) terms, by the pigeonhole principle,
we necessarily have a term a(n) >= 2^(k+2) + 2*k + 3.
- But we also know that a(n) <= 2^(k+2) + e(2^(k+2)) = 2^(k+2) + k + 2.
- This is a contradiction - QED.
Conjecture: this permutation has only finite cycles because it appears that for each interval a(1..2^m) the maximal observed displacement is smaller than 2^m and this maximal displacement is realized by only one element in this interval for m > 3. - Thomas Scheuerle, Oct 22 2022

Examples

			The first terms, alongside their Hamming weight and the values not yet in the sequence so far, are:
  n   a(n)  A000120(a(n))  values not yet in the sequence
  --  ----  -------------  ---------------------------------------------
   1     1              1  { 2,  3,  4,  5,  6,  7,  8,  9, 10, 11, ...}
   2     2              1  { 3,  4,  5,  6,  7,  8,  9, 10, 11, 12, ...}
   3     3              2  { 4,  5,  6,  7,  8,  9, 10, 11, 12, 13, ...}
   4     5              2  { 4,  6,  7,  8,  9, 10, 11, 12, 13, 14, ...}
   5     6              2  { 4,  7,  8,  9, 10, 11, 12, 13, 14, 15, ...}
   6     7              3  { 4,  8,  9, 10, 11, 12, 13, 14, 15, 16, ...}
   7     9              2  { 4,  8, 10, 11, 12, 13, 14, 15, 16, 17, ...}
   8     8              1  { 4, 10, 11, 12, 13, 14, 15, 16, 17, 18, ...}
   9     4              1  {10, 11, 12, 13, 14, 15, 16, 17, 18, 19, ...}
  10    10              2  {11, 12, 13, 14, 15, 16, 17, 18, 19, 20, ...}
  11    12              2  {11, 13, 14, 15, 16, 17, 18, 19, 20, 21, ...}
  12    13              3  {11, 14, 15, 16, 17, 18, 19, 20, 21, 22, ...}
  13    15              4  {11, 14, 16, 17, 18, 19, 20, 21, 22, 23, ...}
  14    17              2  {11, 14, 16, 18, 19, 20, 21, 22, 23, 24, ...}
  15    14              3  {11, 16, 18, 19, 20, 21, 22, 23, 24, 25, ...}
  16    18              2  {11, 16, 19, 20, 21, 22, 23, 24, 25, 26, ...}

Links

Crossrefs

Cf. A000120, A000523, A132753, A217122, A357993, A358057 (inverse).

Programs

  • MATLAB
    function a = A357961( max_n )
    a = 1;
    num = [2:max_n*floor(log2(max_n))];
    for n = 2:max_n
        k = num(length(find(bitget(a(n-1),1:64)==1)));
        a(n) = k; num(num == k) = [];
    end
end % Thomas Scheuerle, Oct 22 2022
  • PARI
    See Links section.

Formula

a(n) <= n + A000523(n).
Empirically: a(n) = n + A000523(n) iff n = 1 or n belong to A132753 \ {3, 4}.
Showing 1-3 of 3 results.

Started in 1964 by Neil J. A. Sloane | Maintained by The OEIS Foundation Inc.

Content is available under The OEIS End-User License Agreement.