cp's OEIS Frontend

Or, binary irreducible polynomials, interpreted as binary vectors, then written in base 10.

The numbers {a(n)} are a subset of the set {A206074}. - Thomas Ordowski, Feb 21 2014

2^n - 1 is a term if and only if n = 2 or n is a prime and 2 is a primitive root modulo n. - Jianing Song, May 10 2021

For odd k, k is a term if and only if binary_reverse(k) = A145341((k+1)/2) is. - Joerg Arndt and Jianing Song, May 10 2021

"Product" refers to the ordinary multiplication of integers.

Differs from A235042 and A236837 for the first time at n=25, where a(n)=25, while A235042(25)=5 and A236837(25)=0. Thus A234741(A234742(n)) = n up to n=24.

a(n) >= n. [All terms of the table A061858 are nonnegative as the product of multiplying two numbers with carries is never less than when multiplying them without carries.]

Specifically, for all n, a(A091209(n)) > A091209(n).

a(A091209(n)) is always composite and, by the above inequality, larger than A091209(n), which implies that none of the terms of A091209 occur in this sequence. Cf. also A236844.

Starting with various terms (primes) in A235033 and iterating the map A234742, we get 5 -> 9 -> 21 -> 49 -> 77 -> 177 -> 333 = a(333).

Another example: 17 -> 81 -> 169 -> 309 -> 721 = a(721).

Does every chain of such iterations eventually reach a fixed point? (One of the terms of A235035.) Or do some of them manage to avoid such "traps" indefinitely? (Note how the terms of A235035 seem to get rarer, but only rather slowly.)

Starting from 23, we get the sequence: 23, 39, 99, 279, 775, 1271, 3003, 26411, 45059, ... which reaches its fixed point, 3643749709604450870616156947649219, after 55 iterations. - M. F. Hasler, Feb 18 2014. [This is now sequence A244323. See also A260729, A260735 and A260441.] - Antti Karttunen, Aug 05 2015

Note also that when coming backwards from some term of such a chain by iterating A234741, we may not necessarily end at the same term we started from.

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.

If n is present, then 2n is present also, as shifting binary representation left never produces any carries.

This is a subsequence of the sequence which gives all such n that A001222(n) = A091222(n).

The fixed points of A234742 are in A235035, thus the latter gives the zeros of this sequence.

It is not known whether the sequence is well-defined for all values. For example, does a(455) or a(1361) have a finite value? Cf. sequences A260735 and A260441.

All terms are divisible by 4.

The sequence reaches its fixed point at a(55) = 3643749709604450870616156947649219, after which the sequence stays constant, a(55) = a(56) = a(57), etc.

Note that a number occurs both here and in A265749 if and only if it is a good match both with its predecessor and the successor in A266195.

Note that a number occurs both here and in A265748 if it is a good match both with its precedent and the successor in A266195.