# Binary expansion and partition numbers [closed]

Not sure if it's correct to ask such a question on this site, but let's try.

Let a(n) be a sequence of positive integer such that a(1) = 1. To reproduce the sequence a(n) through itself, use the following rule: if binary 1xyz is a term then so are 110xyz and 1XYZ where the last one is the same as 1xyz with rewrite 1 -> 10.

The sequence begins with

1, 2, 4, 6, 8, 12, 16, 20, 24, 26, 32, 40, 48, 52

These numbers in binary:

[1]
[1, 0]
[1, 0, 0]
[1, 1, 0]
[1, 0, 0, 0]
[1, 1, 0, 0]
[1, 0, 0, 0, 0]
[1, 0, 1, 0, 0]
[1, 1, 0, 0, 0]
[1, 1, 0, 1, 0]
[1, 0, 0, 0, 0, 0]
[1, 0, 1, 0, 0, 0]
[1, 1, 0, 0, 0, 0]
[1, 1, 0, 1, 0, 0]


Here are examples:

• 1 -> 10 by the rule 1xyz -> 1XYZ (rewrite 1 -> 10)
• 10 -> 100 by the rule 1xyz -> 1XYZ (rewrite 1 -> 10)
• 1 -> 110 by the rule 1xyz -> 110xyz
• 100 -> 1000 by the rule 1xyz -> 1XYZ (rewrite 1 -> 10)
• 10 -> 1100 by the rule 1xyz -> 110xyz
• 1000 -> 10000 by the rule 1xyz -> 1XYZ (rewrite 1 -> 10)
• 110 -> 10100 by the rule 1xyz -> 1XYZ (rewrite 1 -> 10)
• 100 -> 11000 by the rule 1xyz -> 110xyz
• 110 -> 11010 by the rule 1xyz -> 110xyz
• 10000 -> 100000 by the rule 1xyz -> 1XYZ (rewrite 1 -> 10)
• 1100 -> 101000 by the rule 1xyz -> 1XYZ (rewrite 1 -> 10)
• 1000 -> 110000 by the rule 1xyz -> 110xyz
• 1100 -> 110100 by the rule 1xyz -> 110xyz

It appears that positions of the powers of 2 in a(n) are partition numbers (A000041).

I tried to write an efficient PARI/GP program to generate a list of the first n terms and this is what I got:

b1(n) = my(L = logint(n, 2), A = n); A -= 2^L; L - if(A==0, 1, logint(A, 2))
upto(n) = my(v1, v2); v1 = vector(n, i, if(i < 3, i)); v2 = [1, 2];  my(k = 2, j = 1, q = 0); for(i = 3, n, my(A = v2[j] + q); if(A >= v2[k-1], k++; v1[i] = 2^(k-1); j=k\2; q = 0; v2 = concat(v2, i), v1[i] = v1[A] + 2^(j-1) + 2^(k - 1); if((k - j - 2) >= b1(v1[A+1]), j++; q = 0, q++))); v1


Is there a way to write a simpler program (that is, such a program which returns same number of values faster than my program given above)?

• How do you define simpler? All challenges on this site, including tips, need an objective winning criteria Commented Oct 12, 2023 at 10:09
• I don't get it, what order?
– l4m2
Commented Oct 12, 2023 at 11:14
• or can you give first few elements?
– l4m2
Commented Oct 12, 2023 at 11:15
• Welcome to Code Golf! Commented Oct 12, 2023 at 13:16
• These seem to be binary expansions where the lengths of the runs of zeroes are in sorted order. Specifically, ones of the form $110^a10^b10^c\cdots$ where $1\leq a \leq b \leq c \cdots$.
– xnor
Commented Oct 12, 2023 at 17:06

# Rust

Port of @l4m2's c++ answer in Rust.

Try it online!

fn foo(p: i32, x: u128, lb: i32, pos: &mut usize, arr: &mut Vec<u128>) {
if *pos >= arr.len() {
return;
}

if p >= lb {
arr[*pos] = x;
*pos += 1;
}

for k in ((lb + 1)..=p).rev() {
foo(p - k, x | ((1 as u128) << (p - k)), k, pos, arr);
}
}
fn solve(arr: &mut Vec<u128>) {
let mut pos: usize = 0;
let mut p = 0;

loop {
if pos >= arr.len() {
break;
}
foo(p, (1 as u128) << p, 0, &mut pos, arr);
p += 1;
}
}

fn main() {
let n = 50_000_00;
let mut a = vec![0; n];
solve(&mut a);

let mut i = 1;
while i < n {
println!("{:12} {:016X}{:016X}", i, (a[i] >> 64) as u64, (a[i] & 0xFFFFFFFFFFFFFFFF) as u64);
i *= 2;
}
println!("{:12} {:016X}{:016X}", n-1, (a[n-1] >> 64) as u64, (a[n-1] & 0xFFFFFFFFFFFFFFFF) as u64);
}

• Why isn't 26 in your output? Also, should 50_000_00 have an extra 0?
– Neil
Commented Oct 12, 2023 at 18:01

# Charcoal, 52 bytes, 10,000 in ~10s on TIO

⊞υ¹ＦＮ«≔⌊υι⟦Ｉι⟧≔⁻υ⟦ι⟧υ≔⍘ι²ι⊞υ⍘⪫⪪ι1¦10²⊞υ⍘⁺110✂ι¹Ｌι¹¦²


Try it online! Link is to verbose version of code. Explanation: For each number, generates the two derived numbers, and then takes the minimum number generated for the next number.

⊞υ¹


Start with 1.

ＦＮ«


Generate n numbers.

≔⌊υι


Get the next minimum.

⟦Ｉι⟧


Write it to the canvas.

≔⁻υ⟦ι⟧υ


Remove it from the list.

≔⍘ι²ι


Convert it to binary.

⊞υ⍘⪫⪪ι1¦10²


Change all 1s into 10s, convert from binary, and push the result to the list.

⊞υ⍘⁺110✂ι¹Ｌι¹¦²


Remove the leading 1, prefix 110, convert from binary, and push the result to the list.