Advanced Binary Number System

Question

Your task is to write a program that calculates the amount of different ways to display any given whole positive number using the following rules:

Meet the 'advanced binary system':

Any whole positive number can be displayed in binary form, but each bit can have every number from 0 to 9. This means, a valid number might look like this: 480 and would be calculated to 4 * 2^2 + 8 * 2^1 + 0 * 2^0 = 32. You see, every 'bit' is multiplied with 2 to the power of the significance of the bit, just like in binary but with 10 (0 to 9) different possible bits instead of 2 (0 and 1).

It is given a whole positive decimal number in any kind of form. This can be text input, a variable value, an array element, etc. Then your program calculates in how many ways (using the number format explained above. Leading zeroes obviously do not count) the inputted decimal number can be displayed. The result should then be returned, printed or drawn in any readable way as a decimal number.

Examples:

Input: 3 -> Output: 2 > Reason: the decimal number 3 can be displayed as 11 (1 * 2^1 + 1 * 2^0) and as 3 (3 * 2^0), thus 2 different possibilities

Input: 1 -> Output: 1 > Reason: the only possibility is 1 (1 * 2^0)

Input: 2 -> Output: 2 > Reason: possibilities are 10 and 2

And so on.

This is code golf: program with least amount of bytes wins!

Test cases

The first 30 values are:

1, 2, 2, 4, 4, 6, 6, 10, 10, 13, 13, 18, 18, 22, 22, 30, 30, 36, 36, 45, 45, 52, 52, 64, 64, 72, 72, 84, 84, 93

Note that this sequence 1, 1, 2, 2, 4, 4, 6, 6, 10, 10, ... initially matches https://oeis.org/A018819 which counts number of partitions of n into powers of 2, but limiting the digits to 9 causes it to continue 13, 13, 18, 18, ... rather than 14, 14, 20, 20, .... — xnor, Sep 16, 2022 at 21:50
I think this isn't actually a dupe of the challenge to enumerate these base representations, because just counting them allows shortcuts as seen in mine and especially dingledooper's Python answers. — xnor, Sep 17, 2022 at 3:32
Is there a word for a number with digits larger than its base? Like "denormalized"? I googled some but didn't find anything. (You might not even call it a "base" anymore, just a set of place-values.) I guess you could also look at the digits as coefficients for a polynomial which you're evaluating at x=2. Fun fact: a bigint can be thought of as a number in base 2^64, with each chunk as a digit. Or depending on the implementation, 2^30, allowing room for digits to exceed the base w/o overflow, deferring normalization to allow efficient SIMD — Peter Cordes, Sep 18, 2022 at 6:14
@PeterCordes: perhaps you're looking for the term "non-standard positional numeral system", many of which use a set of D digits that is greater than its base B. The non-standard positional numeral system I encounter most frequently is signed-digit binary, which uses 3 digits N0P representing -1, 0, and +1, used in in Booth's multiplication algorithm. It defers normalization to canonical non-adjacent form. — David Cary, Sep 19, 2022 at 21:48

dingledooper · Accepted Answer · 2022-09-16 22:59:50Z

8

Python 2, 45 bytes

Based on the conjectured formula presented in OEIS A309616.

f=lambda n:n<2or-f(n/2-5)*(n>9)+f(n-2)+f(n/2)

Try it online!

answered Sep 16, 2022 at 22:59

dingledooper

22.3k1 gold badge34 silver badges119 bronze badges

7

\$\begingroup\$ Nice find! The conjecture is true and isn't hard to show, by the way. Let \$n>9\$ be even, and write \$n=2k\$. Then, using your \$f\$, we have \$f(n)=f(k-4)+f(k-3)+f(k-2)+f(k-1)+f(k)\$. Likewise, \$f(n-2)=f(k-5)+f(k-4)+f(k-3)+f(k-2)+f(k-1)\$, and subtracting these gives \$f(n)-f(n-2) = f(k)-f(k-5) = f(n/2)-f(n/2-5)\$ as desired. For odd \$n\$, just replace \$n\$ with \$n-1\$, which doesn't change \$f(n)\$ or \$f(n-2)\$ or \$n/2\$ if we floor-divide. \$\endgroup\$
– xnor
Sep 17, 2022 at 7:39
1

\$\begingroup\$ Maybe a bit more directly: For \$n>9\$, list out the advanced binary forms of \$n-1\$ and \$n\$ respectively. There are "easy" pairs where we just increment the last digit of one for \$n-1\$ to get one for \$n\$. For \$n\$ odd, they all pair off this way, so \$f(n-1)=f(n)\$. But, for \$n\$ even, there are unmatched extras: where a form for \$n\$ ends in 0 or one for \$n-1\$ ends in 9. There's \$f(n/2)\$ of the former and \$f((n-10)/2)\$ of the latter. So, the difference in sizes gives \$f(n)-f(n-1)= f(n/2)-f((n-10)/2)\$. Adjusting with \$f(n-1)=f(n-2)\$ gives \$f(n)=f(n-1)+f(n/2)-f(n/2-5)\$. \$\endgroup\$
– xnor
Sep 18, 2022 at 6:03
\$\begingroup\$ @xnor Wow! Super nice! Thanks for posting all that! \$\endgroup\$
– Squareoot
Nov 21, 2022 at 22:51

Add a comment |

xnor · Accepted Answer · 2022-09-17 00:17:02Z

7

Python, 53 bytes

f=lambda n:sum(f(k)for k in range(n)if~9<2*k-n<1)or 1

Try it online!

The if condition is golfed from 0<=n-2*k<=9.

Python, 46 bytes

f=lambda n:sum(map(f,range(n//2+1)[-5:n]),n<1)

Try it online!

-2 by dingledooper

edited Sep 17, 2022 at 0:17

answered Sep 16, 2022 at 22:14

xnor

144k26 gold badges273 silver badges637 bronze badges

1

\$\begingroup\$ You can drop the 0, argument in range. Integer division in Python 2 could also save a byte. I was not aware that ranges could be sliced! \$\endgroup\$
– dingledooper
Sep 16, 2022 at 23:47
1

\$\begingroup\$ @dingledooper Nice catch. Yeah, ranges in Python 3 aren't always awful, mostly just with concatenation! \$\endgroup\$
– xnor
Sep 16, 2022 at 23:53

Add a comment |

caird coinheringaahin g · Accepted Answer · 2022-09-17 01:51:52Z

Jelly, 6 bytes

BḌRDḄċ

Try it online!

How it works

For the input \$x\$, we generate the range \$[1, n]\$, where \$n\$ is the binary representation of \$x\$, treated as decimal. For example: \$x = 3\$ yields \$n = 11\$ and \$x = 6\$ yields \$n = 110\$. We then convert each number in this range to its decimal digits, convert them back to binary, and count the occurrences of \$x\$.

We use the fact that Jelly's base converter doesn't care about the digit values, and simply sums up \$a \times b^n\$ for digit \$a\$, base \$b\$ and position \$n\$.

BḌRDḄċ - Main link. Takes x on the left
B      - Convert x to binary
 Ḍ     - Treat this binary representation as a base 10 number, n
  R    - Range from 1 to n
   D   - Convert each to digits
    Ḅ  - Convert the digits to binary
     ċ - Count occurrences of x

lyxal · Accepted Answer · 2022-09-17 00:46:53Z

4

Vyxal, 5 bytes

↵2vβO

Try it Online!

Times out after default time online for anything over 4, times out for all inputs over 5 after maximum time.

Kind of similar to caird's jelly answer but much slower.

Explained

↵2vβO
↵      # 10 to the power of the input - this will always be longer than the binary representation of the input
 2vβ   # convert each item in the range [1, that] to base 2 - the base converter just happens to be nice with digits greater than the base. 
    O  # Count how many items in that list are equal to the input

answered Sep 17, 2022 at 0:46

lyxal

32.5k2 gold badges56 silver badges138 bronze badges

\$\begingroup\$ ↵vBO should work, but bugs, bugs, bugs, bugs. \$\endgroup\$
– naffetS
Sep 17, 2022 at 3:17
\$\begingroup\$ elif t_item is float or is_sympy(item): return int(item) it's a feature @Steffan \$\endgroup\$
– lyxal
Sep 17, 2022 at 3:29
\$\begingroup\$ it's also useless \$\endgroup\$
– naffetS
Sep 17, 2022 at 16:09

Add a comment |

Arnauld · Accepted Answer · 2022-09-17 12:45:23Z

4

JavaScript (ES6), 35 bytes

Based on the OEIS formula found by dingledooper.

f=n=>n<2?n>=0:f(n-2)+f(n/=2)-f(n-5)

Try it online!

answered Sep 17, 2022 at 12:45

Arnauld

188k20 gold badges171 silver badges630 bronze badges

Add a comment |

CommaToast · Accepted Answer · 2022-09-20 02:06:06Z

Swift:

- 187 bytes (standalone program)

- 66 bytes (function f)

(The question asks for a "program" so providing it as a program.)

import Darwin.C.stdlib
guard let x=CommandLine.arguments.dropFirst().first,let n=Int(x) else {exit(1)}
func f(_ n:Int)->Int{n<1 ?n==0 ?1:0: n%2==0 ?f(n-1):f(n/2)+f(n-1)}
print("\(f(n))")

Try it online!

To get multiple output for a range:

print("\((0...100).map(f))")

Notes:

not that it matters for the sake of this contest, but the compiled & optimized standalone Swift program for arm64 macOS 11+ is 134,440 bytes, and can be downloaded here for inspection; this might seem large but not when you consider that it requires no dependency to be installed also, such as a Python, Java, or Javascript runtime (Swift compiles in a manner similar to C or C++)
if you have Swift installed (for linux/windows/Mac) you can just use the function (and not the full program) directly in the Swift REPL as you would use a function in the Python REPL etc.

The algorithm used is Michael Somos' Haskell answer above for the OEIS sequence.

\$\begingroup\$ Welcome to Code Golf, and nice answer! \$\endgroup\$
– Rydwolf Programs
Sep 20, 2022 at 2:06 — Rydwolf Programs, Sep 20, 2022 at 2:06

Neil · Accepted Answer · 2022-09-17 09:14:12Z

Charcoal, 14 bytes

ＮθＩ№Ｅ⊕⍘θ²⍘Ｉι²θ

Try it online! Link is to verbose version of code. Explanation: Port of @caird's Jelly answer.

Ｎθ              Input `n` as a number
       θ        Input `n`
      ⍘ ²       Convert to a string in base `2`
     ⊕          Increment in base `10`
    Ｅ           Map over implicit range
           ι    Current value
          Ｉ     Cast to string
         ⍘  ²   Interpret as base `2`
   №            Count occurrences of
             θ  Input `n`
  Ｉ             Cast to string
                Implicitly print

I tried to solve this myself but I ended up with a 21 byte port of @xnor's Python answer but using dynamic programming instead of recursion:

⊞υ¹ＦＮ⊞υΣΦυ¬÷⁻⊕ι⊗λχＩ⊟υ

Try it online! Link is to verbose version of code. Explanation:

⊞υ¹

Start with 1 way to produce 0.

ＦＮ

Repeat n times.

⊞υΣΦυ¬÷⁻⊕ι⊗λχ

Get the counts at n/2, n/2-2 ... n/2-8 and take their sum to produce the next count.

Ｉ⊟υ

Output the final count.

naffetS · Accepted Answer · 2022-09-18 00:06:01Z

3

Fig, \$10\log_{256}(96)\approx\$ 8.231 bytes

IxeBefa_Ob

Try it online!

Port of caird's Jelly answer.

answered Sep 18, 2022 at 0:06

naffetS

12.2k2 gold badges17 silver badges48 bronze badges

Add a comment |

Aiden Chow · Accepted Answer · 2022-09-18 01:40:41Z

3

Desmos, 75 bytes

f(n)=∑_{k=0}^{10^N}0^{(n-∑_{j=0}^Nmod(floor(k/10^j),10)2^j)^2}
N=log_2n

Try It On Desmos!

Try It On Desmos! - Prettified

We can golf some bytes, but it'll be super slow (it can't calculate values any higher than around \$n=6\$ in a reasonable amount of time.):

66 bytes

f(n)=∑_{k=0}^{10^n}0^{(n-∑_{j=0}^nmod(floor(k/10^j),10)2^j)^2}

Try It On Desmos!

answered Sep 18, 2022 at 1:40

Aiden Chow

12.7k1 gold badge14 silver badges53 bronze badges

1

\$\begingroup\$ You can use n^4 instead of 10^n. See my PARI/GP answer. \$\endgroup\$
– alephalpha
Sep 18, 2022 at 2:23
1

\$\begingroup\$ @alephalpha that’s very interesting, will fix when I get the chance \$\endgroup\$
– Aiden Chow
Sep 18, 2022 at 7:57

Add a comment |

Noodle9 · Accepted Answer · 2022-09-18 09:19:28Z

3

C (gcc), ^{42 39} 37 bytes

f(n){n=n<1?!n:f(n-2)+f(n/=2)-f(n-5);}

Try it online!

Port of Arnauld's JavaScript answer based on dingledooper's Python answer!!!
Saved 3 bytes thanks to jdt!!!
Saved 2 bytes thanks to alephalpha!!!

edited Sep 18, 2022 at 9:19

answered Sep 17, 2022 at 10:35

Noodle9

19.9k3 gold badges20 silver badges45 bronze badges

1

\$\begingroup\$ 39 bytes port of Arnauld’s port of dingledooper’s formula :-) \$\endgroup\$
– jdt
Sep 17, 2022 at 16:13
1

\$\begingroup\$ @jdt Nice one - thanks! :D \$\endgroup\$
– Noodle9
Sep 17, 2022 at 21:59
1

\$\begingroup\$ f(n){n=n<1?!n:f(n-2)+f(n/=2)-f(n-5);}. \$\endgroup\$
– alephalpha
Sep 18, 2022 at 3:33
1

\$\begingroup\$ @alephalpha Wow, amazing - thanks! :D \$\endgroup\$
– Noodle9
Sep 18, 2022 at 9:20
1

\$\begingroup\$ Don't you need more than just this snippet for this to be able to compile into a program? \$\endgroup\$
– CommaToast
Sep 19, 2022 at 23:27

Add a comment |

alephalpha · Accepted Answer · 2022-09-18 04:35:11Z

PARI/GP, 35 bytes

f(n)=if(n<1,!n,sum(i=0,4,f(n\2-i)))

Attempt This Online!

A port of @xnor's Python answer.

PARI/GP, 42 bytes

n->sum(i=1,n^4,fromdigits(digits(i),2)==n)

Attempt This Online!

A port of @lyxal's Vyxal answer, but uses the upper bound \$n^4\$.

In fact, when \$n>2\$, fromdigits(digits(n,2),10) \$\le 10/9\times10^{\log_2 n}=10/9\times(10^{1/\log2})^{\log n}<(10/9\times10^{1/\log2})^{\log n}<(e^4)^{\log n}=n^4\$. It's easy to see that this is also true when \$n=1,2\$.

HOPS, 28 bytes

A=1-x^9+x*A+(x-x^11)*A@(x^2)

Attempt This Online!

This is not a sequence challenge. I cannot use the IO convention for sequence. But it is still fun to find the generating function. So I won't post this in another answer.

The generating function of this sequence satisfies \$B(x)=(1-x^{10})B(x^2)/(1-x)\$. But we cannot determine the constant term of \$B(x)\$ from this equation.

We know that this constant term is \$1\$. Let \$B(x)=1+x A(x)\$, then we have \$1+x A(x)=(1-x^{10})(1+x^2A(x^2))/(1-x)\$, whence \$A(x)=1-x^9+x A(x)+(x-x^{11})A(x^2)\$.

Kevin Cruijssen · Accepted Answer · 2022-09-18 19:35:11Z

2

05AB1E, 5 bytes

bLCI¢

Try it online or verify all test cases.

Explanation:

b      # Convert the (implicit) input-integer to binary
 L     # Pop and push a list in the range [1,binary(input)]
  C    # Interpret each integer as binary, and convert it to a base-10 integer
   I¢  # Count how many times the input occurs in this list
       # (which is output implicitly as result)

answered Sep 18, 2022 at 19:35

Kevin Cruijssen

123k11 gold badges135 silver badges374 bronze badges

1

\$\begingroup\$ This is crazy haha nice answer \$\endgroup\$
– CommaToast
Sep 20, 2022 at 15:35

Add a comment |

G B · Accepted Answer · 2022-09-19 11:54:58Z

2

Ruby, 40 37 bytes

f=->n{n<1?1:(0..n/2).last(5).sum(&f)}

Try it online!

Based on xnor's answer.

edited Sep 19, 2022 at 11:54

answered Sep 19, 2022 at 11:32

G B

21.3k1 gold badge19 silver badges51 bronze badges

Add a comment |

Kip the Malamute · Accepted Answer · 2023-03-25 12:23:38Z

2

Pyt, 6 bytes

Đɓř2Ĩɔ

Try it online!

Port of caird coinheringaahing's Jelly answer

Đ           implicit input; Đuplicate
 ɓ          convert to ɓinary (automatically casted to decimal number)
  ř         řangify
   2Ĩ       interpret each element of the array as a base-2 Ĩnteger
     ɔ      ɔount occurrences of input in array; implicit print

answered Mar 25 at 12:23

Kip the Malamute

1,6671 silver badge13 bronze badges

Add a comment |

Shaggy · Accepted Answer · 2022-09-19 12:09:46Z

1

Japt `-x`, 10 bytes

ôÂ¢@¶Xì ì2

Try it

answered Sep 19, 2022 at 12:09

Shaggy

41.6k4 gold badges34 silver badges92 bronze badges

Add a comment |

Stack Exchange Network

Advanced Binary Number System

15 Answers 15

Python 2, 45 bytes

Python, 53 bytes

Python, 46 bytes

Jelly, 6 bytes

How it works

Vyxal, 5 bytes

Explained

JavaScript (ES6), 35 bytes

Swift:

- 187 bytes (standalone program)

- 66 bytes (function f)

Charcoal, 14 bytes

Fig, \$10\log_{256}(96)\approx\$ 8.231 bytes

Desmos, 75 bytes

66 bytes

C (gcc), ^{42 39} 37 bytes

PARI/GP, 35 bytes

PARI/GP, 42 bytes

HOPS, 28 bytes

05AB1E, 5 bytes

Ruby, 40 37 bytes

Pyt, 6 bytes

Japt `-x`, 10 bytes

Your Answer

Not the answer you're looking for? Browse other questions tagged
code-golf
number
number-theory
binary
or ask your own question.

Linked

Hot Network Questions

Advanced Binary Number System

15 Answers 15

Python 2, 45 bytes

Python, 53 bytes

Python, 46 bytes

Jelly, 6 bytes

How it works

Vyxal, 5 bytes

Explained

JavaScript (ES6), 35 bytes

Swift:

- 187 bytes (standalone program)

- 66 bytes (function f)

Charcoal, 14 bytes

Fig, \$10\log_{256}(96)\approx\$ 8.231 bytes

Desmos, 75 bytes

66 bytes

C (gcc), 42 39 37 bytes

PARI/GP, 35 bytes

PARI/GP, 42 bytes

HOPS, 28 bytes

05AB1E, 5 bytes

Ruby, 40 37 bytes

Pyt, 6 bytes

Japt -x, 10 bytes

Your Answer

Sign up or log in

Post as a guest

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

Linked

Related

Hot Network Questions

C (gcc), ^{42 39} 37 bytes

Japt `-x`, 10 bytes

Not the answer you're looking for? Browse other questions tagged
code-golf
number
number-theory
binary
or ask your own question.