12
\$\begingroup\$

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.

\$\endgroup\$
4
  • \$\begingroup\$ why is intermediate representation of 3 is [0,0] and not [1,0]? \$\endgroup\$ Oct 6, 2023 at 1:40
  • \$\begingroup\$ @JayantChoudhary Because its binary expansion has no 0s. \$\endgroup\$ Oct 6, 2023 at 2:06
  • 4
    \$\begingroup\$ This is A358372 offset by one. \$\endgroup\$ Oct 6, 2023 at 17:30
  • \$\begingroup\$ Could you show more testcases? \$\endgroup\$
    – tsh
    Oct 7, 2023 at 3:12

12 Answers 12

5
\$\begingroup\$

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

Python, 49 bytes

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

Attempt This Online!

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

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!

\$\endgroup\$
1
  • 1
    \$\begingroup\$ @JonathanAllan thanks. I’d been trying to find something that worked with ¡ but hadn’t quite got there. \$\endgroup\$ Oct 6, 2023 at 17:32
2
\$\begingroup\$

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.

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

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.

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

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

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

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.

\$\endgroup\$
1
  • \$\begingroup\$ You can save one byte // -> / by switching to Python 2. \$\endgroup\$
    – tsh
    Oct 8, 2023 at 7:55
1
\$\begingroup\$

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!

\$\endgroup\$
1
  • 1
    \$\begingroup\$ You can save 4 bytes by using f"{c:b}" instead of f(bin(c)[2:]. \$\endgroup\$
    – The_spider
    Oct 6, 2023 at 19:33
1
\$\begingroup\$

Charcoal, 27 bytes

≔×0NθW№θ0≔⪫E⪪θ1∧κ⍘Lκ²1θI⊕Lθ

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

≔×0Nθ

Start with n 0s.

W№θ0

Repeat until no more 0s are left.

≔⪫E⪪θ1∧κ⍘Lκ²1θ

Convert each run of 0s to binary.

I⊕Lθ

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

24 bytes using the newer version of Charcoal on ATO:

⊞υ×0NW⌈υ≔ΣEυ⪪∧κ⍘Lκ²1υILυ

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

⊞υ×0N

Start with n 0s.

W⌈υ

Repeat until no more 0s are left.

≔ΣEυ⪪∧κ⍘Lκ²1υ

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

ILυ

Output the final length.

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

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.

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

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.

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

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.

\$\endgroup\$
2
  • \$\begingroup\$ 10 bytes \$\endgroup\$
    – Shaggy
    Oct 22, 2023 at 22:20
  • \$\begingroup\$ @Shaggy Wow, that Ò for -~ is pretty obscure and I definitely never would've found ôÍ. Thanks! \$\endgroup\$
    – noodle man
    Oct 22, 2023 at 23:35

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

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