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:

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

• Could you provide some larger test cases? Sep 16, 2022 at 20:59
• 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 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. Sep 19, 2022 at 21:48

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

• 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.
– xnor
Sep 17, 2022 at 7:39
• 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)$.
– xnor
Sep 18, 2022 at 6:03
• @xnor Wow! Super nice! Thanks for posting all that! Nov 21, 2022 at 22:51

# 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

• 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! Sep 16, 2022 at 23:47
• @dingledooper Nice catch. Yeah, ranges in Python 3 aren't always awful, mostly just with concatenation!
– xnor
Sep 16, 2022 at 23:53

# 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


# 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

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

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

# - 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.

• Welcome to Code Golf, and nice answer! Sep 20, 2022 at 2:06

# 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.

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

IxeBefa_Ob


Try it online!

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

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

# C (gcc), 42 39 37 bytes

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


Try it online!

Saved 3 bytes thanks to jdt!!!
Saved 2 bytes thanks to alephalpha!!!

• 39 bytes port of Arnauld’s port of dingledooper’s formula :-)
– jdt
Sep 17, 2022 at 16:13
• @jdt Nice one - thanks! :D Sep 17, 2022 at 21:59
• f(n){n=n<1?!n:f(n-2)+f(n/=2)-f(n-5);}. Sep 18, 2022 at 3:33
• @alephalpha Wow, amazing - thanks! :D Sep 18, 2022 at 9:20
• Don't you need more than just this snippet for this to be able to compile into a program? Sep 19, 2022 at 23:27

# 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)\$$.

# 05AB1E, 5 bytes

bLCI¢


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)

• This is crazy haha nice answer Sep 20, 2022 at 15:35

# Ruby, 40 37 bytes

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


Try it online!

# Pyt, 6 bytes

Đɓř2Ĩɔ


Try it online!

Đ           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


# Japt-x, 10 bytes

ôÂ¢@¶Xì ì2


Try it