# Objective

Given a nonnegative integer, calculate its NDos-size as defined below, and output it.

# NDos' numeral system

The concept of NDos-size comes from the numeral system I made. It represents every nonnegative integer by a nested list, as follows:

• With the binary expansion of given nonnegative integer, each entry of the corresponding NDos-numeral stands for each set bit (1). The order of the entries is LSB-first.
• The content of each entry is, recursively, the NDos-numeral of the number of the trailing 0s of the 1 that the entry stands for, counted till the end or another 1.

For illustrative purposes, here are representations of few integers in NDos' numeral system:

Integer = Binary = Intermediate representation = NDos-numeral

0 = []
1 = 1 =  = [[]]
2 = 10 =  = [[[]]]
3 = 11 = [0, 0] = [[], []]
4 = 100 =  = [[[[]]]]
5 = 101 = [0, 1] = [[], [[]]]
6 = 110 = [1, 0] = [[[]], []]
7 = 111 = [0, 0, 0] = [[], [], []]
8 = 1000 =  = [[[], []]]
9 = 1001 = [0, 2] = [[], [[[]]]]


The NDos-size of the given integer is the number of pairs of square brackets of the corresponding NDos-numeral. That gives the NDos-size of few integers as:

0 -> 1
1 -> 2
2 -> 3
3 -> 3
4 -> 4
5 -> 4
6 -> 4
7 -> 4
8 -> 4
9 -> 5


Note that this sequence is not monotone. 18 -> 6 and 24 -> 5 are one counterexample.

# I/O format

Flexible. Standard loopholes apply.

Be careful not to abuse this loophole. For example, you cannot just input an NDos-numeral as a string and count its left brackets.

• why is intermediate representation of 3 is [0,0] and not [1,0]? Oct 6 at 1:40
• @JayantChoudhary Because its binary expansion has no 0s. Oct 6 at 2:06
• This is A358372 offset by one. Oct 6 at 17:30
– tsh
Oct 7 at 3:12

# 05AB1E, 9 bytes

λNb1¡€g₅O


## Explanation

Recursively generates the sequence of NDos-sizes for all numbers.

Note that if in the encoding we split by 1s and count the size of each part, we'll get the same intermediate representation except an additional 0. But that additional 0 is good, because it accounts for the +1 we need for the outer pair of brackets.

λ        # recursive environment, with base case a(0)=1
N        # push the current index
b        # convert it to binary
1¡       # split on ones
€g       # push the size of each part
₅        # recursively calculate a(i) for each part size
O        # and sum


# Python, 49 bytes

f=lambda n:n<1or f(d:=len(bin(n&-n))-3)+f(n>>d+1)


Attempt This Online!

# Jelly, 10 9 bytes

Bṣ1Ẉß€Ḋ¡S


Try it online!

A monadic link that takes and returns an integer. Written independently of @CommandMaster’s 05AB1E answer but uses effectively the same method.

Thanks to @JonathanAllan for saving a byte!

• @JonathanAllan thanks. I’d been trying to find something that worked with ¡ but hadn’t quite got there. Oct 6 at 17:32

# Retina 0.8.2, 37 bytes

.+
1$&$*0
{0?1
#
0
1
}+(1+)\1
$+0 #  Try it online! Link includes test cases. Explanation: .+ 1$&$*0  Start with the binary representation of 2ⁿ. 0?1 #  Keep a running total of the number of 1 bits. The 0? is part of the unary to binary conversion below. (See the Retina tutorial.) 0 1 +(1+)\1$+0


Convert the 0s from unary to binary.

{
}


Repeat until there are no more bits to process.

#


Output the total number of 1 bits generated.

# Python, 65 57 bytes

-8 thanks to @bsoelch

f=lambda x:sum(map(f,map(len,f"{x:b}".split('1')[1:])))+1


Attempt This Online!

Recursively calculates the NDos-size.

• 57 bytes Oct 6 at 10:05
• You can save a byte by using bin(x) instead of f"{x:b}". The [1:] will remove the 0b prefix as well
– ovs
Oct 6 at 14:17

# JavaScript (Node.js), 37 bytes

f=(x,i)=>x?f(x>>1,~x%2*~i)+x%2*f(i):1


Try it online!

-1 byte as suggested by l4m2

# Python, 46 bytes

f=lambda n,a=0:n<1or n%2*f(a)+f(n//2,~n%2*-~a)


Attempt This Online!

Essentially a port of @tsh's JS. But also fairly similar to @ovs's Python.

• You can save one byte // -> / by switching to Python 2.
– tsh
Oct 8 at 7:55

# Python3, 107 bytes:

lambda x:f(bin(x)[2:])
f=lambda x,c=0:x in['','0']or(f(bin(c)[2:])+f(x[:-1])if'1'==x[-1]else f(x[:-1],c+1))


Try it online!

• You can save 4 bytes by using f"{c:b}" instead of f(bin(c)[2:]. Oct 6 at 19:33

# Charcoal, 27 bytes

≔×0ＮθＷ№θ0≔⪫Ｅ⪪θ1∧κ⍘Ｌκ²1θＩ⊕Ｌθ


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

≔×0Ｎθ


Start with n 0s.

Ｗ№θ0


Repeat until no more 0s are left.

≔⪫Ｅ⪪θ1∧κ⍘Ｌκ²1θ


Convert each run of 0s to binary.

Ｉ⊕Ｌθ


Output the final number of 1s plus one for the containing list.

24 bytes using the newer version of Charcoal on ATO:

⊞υ×0ＮＷ⌈υ≔ΣＥυ⪪∧κ⍘Ｌκ²1υＩＬυ


Attempt This Online! Link is to verbose version of code. Explanation:

⊞υ×0Ｎ


Start with n 0s.

Ｗ⌈υ


Repeat until no more 0s are left.

≔ΣＥυ⪪∧κ⍘Ｌκ²1υ


Convert each string of 0s to binary and split it on 1s.

ＩＬυ


Output the final length.

# Pip, 14 bytes

a?fMS#_MTBa^1o


Attempt This Online!

### Explanation

A full program that calculates the NDos size recursively. Identical approach to Command Master's 05AB1E answer, but discovered independently.

a?fMS#_MTBa^1o
a?             ; Is the argument nonzero?
; If so (recursive case):
TBa    ;  Convert it to binary
^1  ;  Split on 1s
#_M       ;  Take the length of each element
fMS          ;  Map a recursive call to each and sum the results
; Otherwise, the argument is 0 (base case):
o ;  Return 1


Splitting the binary representation on 1s treats it as if there's an extra, empty run of 0s at the beginning. This works out perfectly, since it translates to an extra +1 to the final value, which matches the +1 needed to account for the outer pair of brackets.

# Ruby, 41 bytes

f=->n,k=0{n<1?1:n%2*f[k]+f[n/2,~n%-2*~k]}


Try it online!

### Bonus stage:

The solution is nothing particularly original, (as it often happens), but I went a little deeper down the rabbit hole and found an interesting pattern and put that in the test cases.

I can't prove anything with so little data, but if I perform a run-length encoding of the sequence, then discard the values and keep only the length, the longest run is always 7 9, and the sequence starts from the beginning after 4423 "chunks". Going a little further, the sequence seems to be always the same, and always repeating every 4423 chunks, or 32080 16384 numbers.

I don't think that this pattern will repeat forever, I guess that some arbitrary large n multiplied by 16384 will break the sequence.

# Japt, 12 10 bytes

Ò¢ôÍÅx@ßXÊ


Try it

-2 bytes thanks to two really clever tricks pointed out by Shaggy.

This uses roughly the same method as Command Master’s Python answer.

Ò¢ôÍÅx@ßXÊ­⁡​‎‎⁪⁡⁪⁠⁪⁡⁪‏‏​⁡⁠⁡‌⁢​‎‎⁪⁡⁪⁠⁪⁢⁪‏‏​⁡⁠⁡‌⁣​‎‎⁪⁡⁪⁠⁪⁣⁪‏⁠‎⁪⁡⁪⁠⁪⁤⁪‏‏​⁡⁠⁡‌⁤​‎‎⁪⁡⁪⁠⁪⁢⁡⁪‏‏​⁡⁠⁡‌⁢⁡​‎‎⁪⁡⁪⁠⁪⁢⁢⁪‏⁠‎⁪⁡⁪⁠⁪⁢⁣⁪‏‏​⁡⁠⁡‌⁢⁢​‎‎⁪⁡⁪⁠⁪⁢⁤⁪‏‏​⁡⁠⁡‌⁢⁣​‎‎⁪⁡⁪⁠⁪⁣⁡⁪‏⁠‎⁪⁡⁪⁠⁪⁣⁢⁪‏‏​⁡⁠⁡‌­

• @Shaggy Wow, that Ò for -~ is pretty obscure and I definitely never would've found ôÍ`. Thanks! Oct 22 at 23:35