11
\$\begingroup\$

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
\$\endgroup\$
10
  • 3
    \$\begingroup\$ Could you provide some larger test cases? \$\endgroup\$ Sep 16 at 20:59
  • 4
    \$\begingroup\$ 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, .... \$\endgroup\$
    – xnor
    Sep 16 at 21:50
  • 6
    \$\begingroup\$ 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. \$\endgroup\$
    – xnor
    Sep 17 at 3:32
  • 2
    \$\begingroup\$ 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 \$\endgroup\$ Sep 18 at 6:14
  • 2
    \$\begingroup\$ @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. \$\endgroup\$
    – David Cary
    Sep 19 at 21:48

14 Answers 14

8
\$\begingroup\$

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!

\$\endgroup\$
2
  • 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 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 at 6:03
7
\$\begingroup\$

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

\$\endgroup\$
2
  • 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\$ Sep 16 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 at 23:53
6
\$\begingroup\$

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
\$\endgroup\$
4
\$\begingroup\$

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 
\$\endgroup\$
3
  • \$\begingroup\$ ↵vBO should work, but bugs, bugs, bugs, bugs. \$\endgroup\$
    – Steffan
    Sep 17 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 at 3:29
  • \$\begingroup\$ it's also useless \$\endgroup\$
    – Steffan
    Sep 17 at 16:09
4
\$\begingroup\$

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!

\$\endgroup\$
3
\$\begingroup\$

Charcoal, 14 bytes

NθI№E⊕⍘θ²⍘Iι²θ

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

Nθ              Input `n` as a number
       θ        Input `n`
      ⍘ ²       Convert to a string in base `2`
     ⊕          Increment in base `10`
    E           Map over implicit range
           ι    Current value
          I     Cast to string
         ⍘  ²   Interpret as base `2`
   №            Count occurrences of
             θ  Input `n`
  I             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:

⊞υ¹FN⊞υΣΦυ¬÷⁻⊕ι⊗λχI⊟υ

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

⊞υ¹

Start with 1 way to produce 0.

FN

Repeat n times.

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

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

I⊟υ

Output the final count.

\$\endgroup\$
3
\$\begingroup\$

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!

\$\endgroup\$
2
  • 1
    \$\begingroup\$ You can use n^4 instead of 10^n. See my PARI/GP answer. \$\endgroup\$
    – alephalpha
    Sep 18 at 2:23
  • 1
    \$\begingroup\$ @alephalpha that’s very interesting, will fix when I get the chance \$\endgroup\$
    – Aiden Chow
    Sep 18 at 7:57
3
\$\begingroup\$

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!!!

\$\endgroup\$
5
  • 1
    \$\begingroup\$ 39 bytes port of Arnauld’s port of dingledooper’s formula :-) \$\endgroup\$
    – jdt
    Sep 17 at 16:13
  • 1
    \$\begingroup\$ @jdt Nice one - thanks! :D \$\endgroup\$
    – Noodle9
    Sep 17 at 21:59
  • 1
    \$\begingroup\$ f(n){n=n<1?!n:f(n-2)+f(n/=2)-f(n-5);}. \$\endgroup\$
    – alephalpha
    Sep 18 at 3:33
  • 1
    \$\begingroup\$ @alephalpha Wow, amazing - thanks! :D \$\endgroup\$
    – Noodle9
    Sep 18 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 at 23:27
3
\$\begingroup\$

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.

\$\endgroup\$
1
  • 1
    \$\begingroup\$ Welcome to Code Golf, and nice answer! \$\endgroup\$ Sep 20 at 2:06
2
\$\begingroup\$

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

IxeBefa_Ob

Try it online!

Port of caird's Jelly answer.

\$\endgroup\$
2
\$\begingroup\$

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 challenge. I cannot use the IO convention for . 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)\$.

\$\endgroup\$
2
\$\begingroup\$

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)
\$\endgroup\$
1
  • 1
    \$\begingroup\$ This is crazy haha nice answer \$\endgroup\$
    – CommaToast
    Sep 20 at 15:35
2
\$\begingroup\$

Ruby, 40 37 bytes

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

Try it online!

Based on xnor's answer.

\$\endgroup\$
1
\$\begingroup\$

Japt -x, 10 bytes

ô¢@¶Xì ì2

Try it

\$\endgroup\$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

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