A266191 -id:A266191 - cp's OEIS frontend

A266195 Match-making permutation: start with a(1) = 1, then always choose for a(n) the least unused number such that multiplying a(n) by a(n-1) does not produce any carries when performed in base 2.

1, 2, 3, 4, 5, 6, 8, 7, 9, 10, 12, 16, 11, 17, 13, 32, 14, 18, 20, 19, 33, 15, 34, 22, 64, 21, 24, 36, 28, 65, 23, 66, 25, 40, 35, 72, 42, 48, 37, 68, 26, 128, 27, 129, 29, 130, 30, 132, 31, 256, 38, 80, 49, 73, 56, 136, 41, 96, 69, 144, 67, 84, 97, 137, 112, 145, 134, 160, 50, 133, 76, 161, 100, 257, 39, 258, 43, 260, 44

Offset: 1

Antti Karttunen, Dec 26 2015

More formally: the lexicographically earliest injection of natural numbers such that for any n > 1, A061858(a(n), a(n-1)) = 0; a(1) = 1. By necessity also surjective on N (see below for why), thus a bijection.
Less formally:
In this context we say that two positive natural numbers x and y "match", when they will not produce any carries when multiplied in binary system (see the Examples). The purpose of this sequence is with a simple greedy algorithm to form pairs of natural numbers that "match to each other" according to that criterion. Note that each number after 1 will satisfy the matching condition both with its predecessor and its successor.
For the sake of this discussion, we call a natural number n "dense" if the density of 1-bits in its binary representation (cf., e.g., A265917) is over a certain threshold, whose exact value we leave undefined, but can be subjectively gauged. In contrast, we call a number "ethereal" if its base-2 representation consists mostly of zeros. E.g., 258 = 100000010_2 is clearly one of the "ethereals", while 43 = 101011_2, is definitely on the denser side.
When running the algorithm, we note that after a while, for long stretches of time, it mostly matches "dense" numbers with "ethereal" numbers, like 258 and 43, which occur next to each other in the sequence as a(76) and a(77), and also a(49)=31 and a(50)=256, which are the most dense and most ethereal members of their respective binary sizes (see the Example section).
Also, it should be obvious that each number of the form 2^k (terms of A000079, the "super-ethereals") occur as the first representative of the numbers of the same binary length, and any number of the form (2^k)-1 (A000225, "super-dense") comes as the last of the numbers of binary length k.
No matter how dense some number might look to us, there is always a sufficiently ethereal number with which it can be mated (that is, the algorithm is never stuck, because it can always try the next unused super-ethereal 2^k if everything else fails). Moreover, whenever that next 2^k has appeared, it also always immediately picks up from the backlog of (more or less dense) numbers the least unmatched number so far, which proves that no number is left out, and the sequence is indeed a permutation of the natural numbers.
However, certain numbers intuitively feel to be much better matches to each other, like 10 and 12 (cf. Examples), because they are not so distant from each other. We define "good matches" to be such pairs that the binary length (A070939) of the numbers is equal. As 10 and 12 are both four bits long, they are one instance of such a good match. Note that 10 is also a good match with the immediately preceding number in the sequence, 9 = 1001_2.
Sequence A266197 gives the positions of these good matches, and A265748 & A265749 give their first and second members respectively. It is an open question whether the algorithm generates an infinite number of good matches or not.

			For n=11, we first note that a(10) = 10, and the least unused number after a(1) .. a(10) is 11. Trying to multiply 10 (= 1010_2) and 11 (= 1011_2), in the binary system results in
     1011
  *  1010
  -------
   c1011
  1011
  -------
  1101110 = 110,
and we see that there's a carry-bit (marked c) affecting the result, thus A048720(10,11) < 10*11 and A061858(10,10) > 0, thus we cannot select 11 for a(11).
The next unused number is 12, and indeed, for numbers 10 and 12 (= 1100_2), the binary multiplication results in
     1100
  *  1010
  -------
    1100
  1100
  -------
  1111000 = 120,
which is a clean product without carries (i.e., A061858(10,12) = 0), thus 12 is selected to be a match for 10, and we set a(11) = 12.
For a(49) = 31 (= 11111_2) and a(50) = 256 (= 100000000_2) the multiplication results in
      100000000
    *     11111
  -------------
      100000000
     100000000
    100000000
   100000000
  100000000
  -------------
  1111100000000 = 7936,
and we see that the carryless product is this time obtained almost trivially, as the other number is so much larger and more spacious than the other that they can easily avoid any clashing bits that would produce carries.

Antti Karttunen, Table of n, a(n) for n = 1..2694
Eric Angelini, a(n)*a(n+1) shows at least twice the same digit, Posting on SeqFan-list Dec 21 2015. [Source of inspiration for this sequence.]
Rémy Sigrist, Logarithmic scatterplot of the first 500000 terms
Index entries for sequences that are permutations of the natural numbers

Inverse permutation: A266196.
Cf. A000079, A000225, A048720, A061858, A070939, A265917.
Cf. A266194 (products of these pairs).
Cf. A266197 (indices of good matches),
Cf. A265748, A265749 (give the first and second members of good matches).
Cf. A266186 (when 2^n appears), A266187 (when (2^n)-1 appears).
Cf. A266191, A266351 (similar permutations).
Cf. also A235034, A235035.

A266121 Lexicographically first injection of natural numbers beginning with a(1)=1 such that 1+(a(n)*a(n+1)) is a fibbinary number (A003714), i.e., has no adjacent 1's in its base-2 representation.

Original entry on oeis.org

1, 3, 5, 4, 2, 8, 9, 7, 12, 6, 14, 24, 11, 13, 20, 16, 10, 26, 40, 17, 15, 39, 28, 19, 27, 25, 23, 48, 22, 30, 44, 31, 33, 32, 18, 36, 29, 47, 45, 52, 21, 55, 49, 84, 61, 43, 51, 53, 80, 34, 64, 37, 35, 59, 75, 117, 93, 91, 57, 41, 100, 82, 50, 104, 42, 98, 106, 90, 114, 72, 58, 144, 65, 63, 151, 56, 38, 54, 76, 71, 60

Offset: 1

Antti Karttunen, Dec 23 2015

It is conjectured that this sequence is not only injective, but also surjective on N, i.e., that it is a true permutation of natural numbers.
A similar sequence, but with condition that "(a(n)*a(n+1)) must be a member of A003714" yields a sequence: 1, 2, 4, 5, 8, 9, 16, 10, 13, 20, ... (A269361) which certainly is not a bijection, because it contains only terms of A091072.
Also, with above condition and the initial value a(1) = 3 the algorithm generates A269363 which contains only terms of A091067. See also A266191.

			After the initial a(1) = 1, for obtaining the value of a(2) we try the first unused number, which is 2, but (1*2)+1 = 3, which in binary is "11", thus 2 is not qualified at this point of time. So next we try 3, and (1*3)+1 = 4, which in binary is "100", and that satisfies our criterion (no adjacent 1-bits), thus we set a(2) = 3.
For a(3), we test with the least unused numbers 2, 4, 5, etc., yielding products (3*2)+1 = 7 = "111", (3*4)+1 = 13 = "1101" and (3*5)+1 = 16 = "10000" in binary, and only 5 satisfies the criterion, thus we set a(3) = 5.

Antti Karttunen, Table of n, a(n) for n = 1..16384
Index entries for sequences that are permutations of the natural numbers

Left inverse: A266122 (also the right inverse if this sequence is a permutation of natural numbers).
Cf. A003714, A003987, A091067, A091072, A269361, A269363, A269365, A269366, A269367.
Cf. also A266191 and A266117 for similar permutations.

Minor typo in the description corrected by Antti Karttunen, Feb 25 2016

A269361 Lexicographically first injection of natural numbers beginning with a(1)=1 such that a(n)*a(n+1) is a fibbinary number (A003714), i.e., has no adjacent 1's in its base-2 representation.

Original entry on oeis.org

1, 2, 4, 5, 8, 9, 16, 10, 13, 20, 17, 32, 18, 29, 36, 33, 40, 26, 21, 49, 42, 52, 25, 41, 50, 82, 57, 45, 53, 80, 34, 64, 37, 113, 74, 125, 84, 61, 72, 58, 73, 65, 68, 69, 128, 66, 129, 132, 133, 77, 114, 81, 117, 90, 104, 85, 98, 89, 93, 100, 105, 161, 106, 97, 169, 122, 137, 157, 138, 136, 121, 141, 149, 221, 153, 109, 160, 116, 144

Offset: 1

Antti Karttunen, Feb 25 2016

The sequence is conjectured to be a permutation of A091072.

Antti Karttunen, Table of n, a(n) for n = 1..65537

Cf. A003714, A091072, A266121, A266191, A269363, A269365, A269366.

A269363 Lexicographically first injection of natural numbers beginning with a(1)=3 such that for all n >= 1, a(n)*a(n+1) is a fibbinary number (A003714), i.e., has no adjacent 1's in its base-2 representation.

Original entry on oeis.org

3, 6, 7, 12, 11, 15, 22, 24, 14, 19, 27, 38, 28, 23, 46, 48, 43, 30, 39, 35, 59, 44, 31, 75, 62, 87, 51, 83, 56, 47, 88, 54, 76, 55, 96, 86, 60, 71, 67, 70, 78, 112, 79, 107, 102, 91, 120, 139, 118, 140, 119, 142, 131, 134, 155, 240, 156, 135, 152, 108, 95, 92, 103, 179, 184, 115, 147, 224, 94, 175, 123, 150, 111, 158, 214, 163, 203

Offset: 1

Antti Karttunen, Feb 25 2016

The sequence is conjectured to be a permutation of A091067.

The scatter plot is quite interesting (essentially the same as A269367). Compare also to the graph of A269361.

Antti Karttunen, Table of n, a(n) for n = 1..65537

Cf. A003714, A003987, A091067, A266121, A266191, A269361, A269365, A269366.

Cf. A269367 (the terms ranked with A255070).

fibbinaryQ[n_] := BitAnd[n, 2 n]==0; a[1]=3; a[n_] := a[n] = For[k=1, True, k++, If[Mod[k, 4] != 1, If[fibbinaryQ[a[n-1] k], If[FreeQ[Array[a, n-1], k], Return[k]]]]]; Table[a[n], {n, 1, 100}] (* Jean-François Alcover, Mar 02 2016 *)

A266117 Lexicographically first injection of positive integers beginning with a(1) such that a(n)*a(n+1) is a term of A265349, i.e., has no multiple occurrences of any nonzero digit when viewed in factorial base (A007623).

Original entry on oeis.org

1, 2, 3, 4, 5, 10, 11, 6, 7, 12, 8, 9, 24, 13, 18, 19, 26, 14, 17, 22, 21, 16, 15, 32, 30, 20, 23, 29, 42, 28, 25, 48, 34, 53, 41, 54, 27, 40, 33, 36, 37, 61, 65, 44, 49, 72, 39, 38, 51, 52, 55, 59, 47, 46, 58, 50, 60, 62, 31, 66, 56, 57, 64, 45, 80, 63, 74, 69, 68, 35, 79, 100, 73, 43, 67, 70, 71, 78, 84, 87, 92, 90, 76, 96, 75

Offset: 1

Antti Karttunen, Dec 22 2015

After a(1) = 1, always choose for a(n+1) the least unused k such that in factorial base representation (A007623), the product a(n)*a(n+1) will not show any of the nonzero digits present twice (or more times), regardless of the positions of the digits.

			For n = 6, we start searching from the least not yet used number in range a(1) .. a(5) [which is 6, because all the previous terms are fixed] for the first number whose product with a(5) = 5 results a number in A265349.
Multiplying 5 (in factorial base "21") with 6 (in factorial base "100") results 30, which in factorial base is "1100", containing digit "1" twice, thus 6 is disqualified.
Similarly, products 5*7, 5*8 and 5*9 result 35 = "1121", 40 = "1220" and 45 = "1311", where in all cases one of the nonzero digits occur more than once, so 7, 8 and 9 are also all disqualified.
But 5*10 = 50, which has a factorial base representation ("2010") that matches the criterion, thus a(6) = 10.

Antti Karttunen, Table of n, a(n) for n = 1..14641
Eric Angelini, a(n)*a(n+1) shows at least twice the same digit, Posting on SeqFan-list Dec 21 2015. [Source of inspiration for this sequence.]
Index entries for sequences related to factorial base representation
Index entries for sequences that are permutations of the natural numbers

Left inverse: A266118 (also the right inverse if this sequence is a permutation of the positive integers).
Cf. A264990, A265349.
Cf. also A266121, A266191 and A266195 for similar permutations.

A300896 Lexicographically earliest sequence of distinct positive terms such that, for any n > 0, a(n) + a(n+1) + a(n+2) is a Fibbinary number (A003714).

Original entry on oeis.org

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

Offset: 1

Rémy Sigrist, Mar 14 2018

This sequence has similarities with A266191: here we consider the sum of triples of consecutive terms, there their product.
This sequence is conjectured to be a permutation of the natural numbers.
See A300890 for a similar sequence.

			The first terms, alongside the binary representation of triples of consecutive terms, are:
  n   a(n)    binary(a(n) + a(n+1) + a(n+2))
  --  ----    ------------------------------
   1     1       1000
   2     2       1010
   3     5      10000
   4     3      10001
   5     8      10010
   6     6      10001
   7     4      10100
   8     7     100000
   9     9     100100
  10    16     100101
  11    11     100001
  12    10     100100
  13    12     101001
  14    14     101010
  15    15    1000000
  16    13    1000010
  17    36    1001000
  18    17    1000000
  19    19    1000001
  20    28    1000010

Rémy Sigrist, Table of n, a(n) for n = 1..10000
Rémy Sigrist, PARI program for A300896

Cf. A003714, A266191, A300890.

PARI
```
See Links section.
```

cp's OEIS Frontend

A266192 a(n) = index of n in A266191 or 0 if n is not present in that sequence.

Views

Author

Keywords

Comments

Links

Crossrefs

A266195 Match-making permutation: start with a(1) = 1, then always choose for a(n) the least unused number such that multiplying a(n) by a(n-1) does not produce any carries when performed in base 2.

Views

Author

Keywords

Comments

Examples

Links

Crossrefs

A266121 Lexicographically first injection of natural numbers beginning with a(1)=1 such that 1+(a(n)*a(n+1)) is a fibbinary number (A003714), i.e., has no adjacent 1's in its base-2 representation.

Views

Author

Keywords

Comments

Examples

Links

Crossrefs

Extensions

A269361 Lexicographically first injection of natural numbers beginning with a(1)=1 such that a(n)*a(n+1) is a fibbinary number (A003714), i.e., has no adjacent 1's in its base-2 representation.

Views

Author

Keywords

Comments

Links

Crossrefs

A269363 Lexicographically first injection of natural numbers beginning with a(1)=3 such that for all n >= 1, a(n)*a(n+1) is a fibbinary number (A003714), i.e., has no adjacent 1's in its base-2 representation.

Views

Author

Keywords

Comments

Links

Crossrefs

Programs

Mathematica

A266117 Lexicographically first injection of positive integers beginning with a(1) such that a(n)*a(n+1) is a term of A265349, i.e., has no multiple occurrences of any nonzero digit when viewed in factorial base (A007623).

Views

Author

Keywords

Comments

Examples

Links

Crossrefs

A300896 Lexicographically earliest sequence of distinct positive terms such that, for any n > 0, a(n) + a(n+1) + a(n+2) is a Fibbinary number (A003714).

Views

Author

Keywords

Comments

Examples

Links

Crossrefs

Programs

PARI