2
\$\begingroup\$

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)?

\$\endgroup\$
7
  • 3
    \$\begingroup\$ How do you define simpler? All challenges on this site, including tips, need an objective winning criteria \$\endgroup\$
    – mousetail
    Oct 12, 2023 at 10:09
  • 2
    \$\begingroup\$ I don't get it, what order? \$\endgroup\$
    – l4m2
    Oct 12, 2023 at 11:14
  • 1
    \$\begingroup\$ or can you give first few elements? \$\endgroup\$
    – l4m2
    Oct 12, 2023 at 11:15
  • 1
    \$\begingroup\$ Welcome to Code Golf! \$\endgroup\$ Oct 12, 2023 at 13:16
  • 1
    \$\begingroup\$ 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\$. \$\endgroup\$
    – xnor
    Oct 12, 2023 at 17:06

2 Answers 2

1
\$\begingroup\$

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);
}
\$\endgroup\$
1
  • \$\begingroup\$ Why isn't 26 in your output? Also, should 50_000_00 have an extra 0? \$\endgroup\$
    – Neil
    Oct 12, 2023 at 18:01
0
\$\begingroup\$

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

⊞υ¹FN«≔⌊υι⟦Iι⟧≔⁻υ⟦ι⟧υ≔⍘ι²ι⊞υ⍘⪫⪪ι1¦10²⊞υ⍘⁺110✂ι¹Lι¹¦²

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.

FN«

Generate n numbers.

≔⌊υι

Get the next minimum.

⟦Iι⟧

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✂ι¹Lι¹¦²

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

\$\endgroup\$

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