14
\$\begingroup\$

Background

A167519: Lexicographically earliest increasing sequence which lists the positions of the zero digits in the sequence.

3, 10, 11, 12, 11000, 11111, 11112, 11113, 11114, 11115, 11116, 11117, 11118, 11119,
11121, 11122, 11123, 11124, 11125, 11126, 11127, 11128, 11129, 11131, 11132, 11133,
11134, 11135, 11136, 11137, 11138, 11139, 11141, 11142, 11143, 11144, ...

If we list the digits, we get

3 1 0 1 1 1 2 1 1 0 0 0 1 1 1 1 1 1 1 1 1 2 1 1 1 1 3 1 1 1 1 4 ...
    ^             ^ ^ ^

The digits at index 3, 10, 11, 12, 11000, ... are zeros, and all the other digits are nonzero.

It looks a bit boring after a few terms. It becomes a bit more interesting if we consider the same sequence in smaller bases:

Base 5

(in base 10)
3, 5, 10, 11, 150, 156, 157, 158, 159, 161, ...

(in base 5)
3, 10, 20, 21, 1100, 1111, 1112, 1113, 1114, 1121, ...

Explanation:

  1. The first term cannot be 1 (the first base-5 digit is 1, not 0) or 2 (the next number would have a leading zero), so it is 3.
  2. The next term cannot be 4 (leading zero), so it must be 5 = 10(5). It satisfies the first term (3rd base-5 digit is 0).
  3. The third term must have at least 2 digits and its 2nd digit is 0. The smallest number that satisfies this is 10 = 20(5).
  4. Another 2-digit number can fit here without causing a leading zero. The smallest such number exceeding 10 is 11 = 21(5).
  5. The next number cannot be 2-digit or 3-digit, so it must have 4 digits, giving 1100(5). We don't have any more zeros for a while, giving a series of zeroless numbers starting with 1111(5).

Base 4

(in base 10)
3, 8, 9, 80, 85, 86, 87, 89, 90, 91, 93, 94, 95, 101, 102, 103, 105, 106, 107,
109, 110, 113, 1344, 16448, 21824, 32833, 34133, 38229, 38230, 38231, ...

(in base 4)
3, 20, 21, 1100, 1111, 1112, 1113, 1121, 1122, 1123, 1131, 1132, 1133, 1211, 1212,
1213, 1221, 1222, 1223, 1231, 1232, 1301, 111000, 10001000, 11111000, 20001001,
20111111, 21111111, 21111112, 21111113, ...
  1. The first term is 3 by the same logic.
  2. The next term cannot be 10(4) due to leading zero, and the next fitting number is 20(4).
  3. The rest goes on by the "long-term logic". The next interesting part comes earlier than in higher bases, so I decided to include it here.

Starting here, the "long-term logic" refers to the following:

  • If the last number has k digits, find the smallest k-digit number that is greater than the last number and has zero digits precisely at the necessary position.
  • If such a number does not exist or it would cause a leading zero in the next term, increase the number of digits until the next term won't have a leading zero, and fill the nonzero digits with 1.

Base 3

(in base 10)
4, 6, 10, 12, 19, 22, 24, 111, 121, 122, 124, 125, 130, 131, 133, 134, 148, 149,
151, 152, 157, 158, 160, 161, 202, 283, 1089, 6921, 6925, 9837, 13482, 13486,
16402, 16403, 16405, 16408, 16411, 16412, 16414, 16415, 16429, 16430, 16432,
16433, 16435, ...

(in base 3)
11, 20, 101, 110, 201, 211, 220, 11010, 11111, 11112, 11121, 11122, 11211, 11212,
11221, 11222, 12111, 12112, 12121, 12122, 12211, 12212, 12221, 12222, 21111,
101111, 1111100, 100111100, 100111111, 111111100, 200111100, 200111111, 211111111,
211111112, 211111121, 211111201, 211111211, 211111212, 211111221, 211111222,
211112111, 211112112, 211112121, 211112122, 211112201, ...
  1. The first term cannot be 3 since it is 10(3) but 2 is not in the sequence. Therefore, the first term is 4 = 11(3).
  2. The sequence goes on with the long-term logic.

Base 2

(in base 10)
2, 4, 5, 7, 31, 63, 127, 191, 255, 511, 1021, 1023, 2047, 4095, 8191, 16383, 28671,
32767, ...

(in base 2)
10, 100, 101, 111, 11111, 111111, 1111111, 10111111, 11111111, 111111111,
1111111101, 1111111111, 11111111111, 111111111111, 1111111111111, 11111111111111,
110111111111111, 111111111111111, ...

Determining the initial terms here is particularly tricky.

  1. The first term is 2 = 10(2) because it satisfies the first zero position.

  2. The next term cannot be 3, but 4 = 100(2) works. This also fixes the next two terms 5 = 101(2) and 7 = 111(2).

  3. The next term should be at least 12, but:

    • 12 doesn't work because <1>100 (<x> marks where 0 has to be)
    • 13 doesn't work because 1<1>01
    • 14 doesn't work because 11<1>0
    • 15 doesn't work because 111<1>

    Therefore the number has at least 5 bits, the first 4 of which must be 1. Then the last bit cannot be 0 either (16 is not in the sequence), so it becomes 31 = 11111(2).

  4. Now the rest follows the long-term logic, except that it continues to grow exponentially. This is because, for every number k, there is only one k-bit number that does not contain 0.

Code used for handcrafting these sequences.

Challenge

Given the base n >= 2, output the sequence generated by the definition of A167519 in base n.

I/O rules apply. You may choose one of the following:

  • Given n, output the terms of the sequence indefinitely;
  • Given n and a 0- or 1-based index k, output the kth term of the sequence n;
  • Given n and a positive integer k, output the first k terms of the sequence n.

If the numbers are output as a string or list-of-digits representation, they may be in base n or a fixed base for all n.

Standard rules apply. The shortest code in bytes wins.

\$\endgroup\$

1 Answer 1

2
\$\begingroup\$

Charcoal, 77 72 bytes

NθNη≔⎇⁼θ²I⪪245¹⟦⁺³⁼³θ⟧υW‹Lυη«⊞υ⌈υ≔1ζW¬⁼⌕Aζ1Φυ‹λLζ≔⪫00⭆⊞Oυ⊕⊟υ⍘λ⭆θ¬νζ»I…υη

Try it online! Link is to verbose version of code. Outputs the first k terms. Explanation:

NθNη

Input n and k.

≔⎇⁼θ²I⪪245¹⟦⁺³⁼³θ⟧υ

If n=2, start with 2, 4, 5, otherwise if n=3 then start with 4 otherwise start with 3.

W‹Lυη«

Repeat until enough terms have been collected.

⊞υ⌈υ

Start with the previous number.

≔1ζ

Start with an invalid base representation, so that the following loop always executes at least once.

W¬⁼⌕Aζ1Φυ‹λLζ

Find the position of all of the 1s in the string (corresponding to the 0s in the actual base representation) and compare this to the values of the list that are less than the length of the string, and until a valid number is found...

≔⪫00⭆⊞Oυ⊕⊟υ⍘λ⭆θ¬νζ

... increment the trial number and convert the list into base n using 1 for the 0 digit and 0 for all other digits. (I could possibly do slightly better with the newer version of Charcoal on ATO.) Join the strings and wrap the entire result in a leading and trailing 0; the leading 0 is for 1-indexing and the trailing 0 is because the next number is known to begin with a non-0 digit.

»I…υη

Output k terms.

\$\endgroup\$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Not the answer you're looking for? Browse other questions tagged or ask your own question.