login
The OEIS Foundation is supported by donations from users of the OEIS and by a grant from the Simons Foundation.

 

Logo


Hints
(Greetings from The On-Line Encyclopedia of Integer Sequences!)
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. 17
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 (list; graph; refs; listen; history; text; internal format)
OFFSET

1,2

COMMENTS

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.

LINKS

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

EXAMPLE

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.

PROG

(Scheme, with defineperm1-macro from Antti Karttunen's IntSeq-library)

;; Warning: this algorithm is quite "dense":

(defineperm1 (A266195 n) (cond ((= 1 n) n) (else (let ((prev (A266195 (- n 1)))) (let loop ((k 1)) (cond ((and (not-lte? (A266196 k) (- n 1)) (zero? (A061858bi k prev))) k) (else (loop (+ 1 k)))))))))

;; In above code (A061858bi x y) is two-argument function returning the difference between x*y - A048720(x, y). See entries A048720 and A061858.

;; We consider a > b (i.e. not less than b) also in case a is #f.

;; (Because of the stateful caching system used by defineperm1-macro):

(define (not-lte? a b) (cond ((not (number? a)) #t) (else (> a b))))

CROSSREFS

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.

Sequence in context: A334433 A334435 A334436 * A102530 A266196 A215501

Adjacent sequences:  A266192 A266193 A266194 * A266196 A266197 A266198

KEYWORD

nonn,base

AUTHOR

Antti Karttunen, Dec 26 2015

STATUS

approved

Lookup | Welcome | Wiki | Register | Music | Plot 2 | Demos | Index | Browse | More | WebCam
Contribute new seq. or comment | Format | Style Sheet | Transforms | Superseeker | Recent
The OEIS Community | Maintained by The OEIS Foundation Inc.

License Agreements, Terms of Use, Privacy Policy. .

Last modified August 9 20:09 EDT 2020. Contains 336326 sequences. (Running on oeis4.)