Calculate NDos-size of given integer

Question

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 = [0] = [[]]
2 = 10 = [1] = [[[]]]
3 = 11 = [0, 0] = [[], []]
4 = 100 = [2] = [[[[]]]]
5 = 101 = [0, 1] = [[], [[]]]
6 = 110 = [1, 0] = [[[]], []]
7 = 111 = [0, 0, 0] = [[], [], []]
8 = 1000 = [3] = [[[], []]]
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.

Answer 1

05AB1E, 9 bytes

λNb1¡€g₅O

Try it online! (or more nicely formatted)

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

Answer 2

Python, 49 bytes

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

Attempt This Online!

Answer 3

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!

Answer 4

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.

Answer 5

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.

Answer 6

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

Answer 7

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.

Answer 8

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!

Answer 9

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.

Answer 10

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.

Answer 11

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.

Answer 12

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Ê­⁡​‎‎⁡⁠⁡‏‏​⁡⁠⁡‌⁢​‎‎⁡⁠⁢‏‏​⁡⁠⁡‌⁣​‎‎⁡⁠⁣‏⁠‎⁡⁠⁤‏‏​⁡⁠⁡‌⁤​‎‎⁡⁠⁢⁡‏‏​⁡⁠⁡‌⁢⁡​‎‎⁡⁠⁢⁢‏⁠‎⁡⁠⁢⁣‏‏​⁡⁠⁡‌⁢⁢​‎‎⁡⁠⁢⁤‏‏​⁡⁠⁡‌⁢⁣​‎‎⁡⁠⁣⁡‏⁠‎⁡⁠⁣⁢‏‏​⁡⁠⁡‌­
Ò            ‎⁡Add 1 to:
 ¢           ‎⁢The input, converted to binary,
  ôÍ         ‎⁣split on elements which are true when inverted.
    Å        ‎⁤Slice this list from index 1 to the end.
     x@      ‎⁢⁡Sum after mapping each X to
       ß     ‎⁢⁢  the result of recursing with
        XÊ   ‎⁢⁣  the length of X as the input.
💎

Created with the help of Luminespire.