26
\$\begingroup\$

A positive integer can be diluted by inserting a 0 between two bits in its binary expansion. This means that an n-bit number has n-1 dilutions, which are not necessarily all distinct.

For example, for 12 (or 1100 in binary), the dilutions are

11000 = 24
   ^

11000 = 24
  ^

10100 = 20
 ^

In this challenge, we're going to be taking the sum of all the dilutions, exclusive of the original number. For 12, taking the sum of 24, 24, 20 results in 68, so 68 should be the output for 12.

Challenge

Given a positive integer n > 1 as input, output/return the diluted sum as explained above.

Examples

in    out
---   ---
2       4
3       5
7      24
12     68
333  5128
512  9216

Rules

  • The input and output can be assumed to fit in your language's native integer type.
  • The input and output can be given in any convenient format.
  • Either a full program or a function are acceptable. If a function, you can return the output rather than printing it.
  • Standard loopholes are forbidden.
  • This is so all usual golfing rules apply, and the shortest code (in bytes) wins.
\$\endgroup\$
  • \$\begingroup\$ Does "any convenient format" include a binary string? \$\endgroup\$ – Shaggy Jan 29 '18 at 15:40
  • 1
    \$\begingroup\$ @Shaggy "Any convenient format" is intended to be inclusive of methods of input/output, not format. As such, I'm going to say no, you must take input as an integer or a string representing that integer. \$\endgroup\$ – AdmBorkBork Jan 29 '18 at 16:02
  • \$\begingroup\$ Nice challenge! \$\endgroup\$ – Manish Kundu Jan 29 '18 at 17:14
  • 1
    \$\begingroup\$ This sequence is currently (30 Jan 2018) not in the OEIS \$\endgroup\$ – Giuseppe Jan 30 '18 at 19:51

22 Answers 22

12
\$\begingroup\$

Python 2, 43 39 bytes

f=lambda n,i=2:n/i and n*2-n%i+f(n,i*2)

Try it online!


How?

Each call of the recursive function calculates a single dilution. The position of the inserted 0 is log2(i). The function recurses until i gets bigger than n and the insertion would be on the left of the number. If i>n, n/i evaluates to 0, which is a falsy value in Python.

n*2 shifts the entire number one binary digit left, n%i or n % 2**(position of insertion) calculates the value of the part that should not be shifted left. This value gets subtracted from the shifted number.

Example (n=7)

call       n/i          bin(n)  n*2     n%i   dilution       return value

f(7, i=2)  3 => truthy  0b111   0b1110  0b1   0b1101 = 13    13 + f(7, 2*2) = 13 + 11 = 24
f(7, i=4)  1 => truthy  0b111   0b1110  0b11  0b1011 = 11    11 + f(7, 4*2) = 11 + 0 = 11
f(7, i=8)  0 => falsy                                        0
\$\endgroup\$
7
\$\begingroup\$

Jelly, 11 bytes

BJṖ2*ɓdḅḤ}S

Try it online!

How it works

BJṖ2*ɓdḅḤ}S  Main link. Argument: n (integer)

B            Binary; convert n to base 2. This yields a digit array A.
 J           Indices; yield [1, ..., len(A)].
  Ṗ          Pop; remove the last element, yielding [1, 2, ..., len(A)-1].
   2*        Elevate 2 to these powers, yielding [2, 4, ..., 2**(len(A)-1)].
             Let's call the result B.
     ɓ       Begin a new, dyadic chain, with left argument n and right argument B.
      d      Divmod; yield [n/b, n%b], for each b in B.
        Ḥ}   Unhalve right; yield 2b for each b in B, i.e., [4, 8, ..., 2**len(A)].
       ḅ     Unbase; convert each [n/b, n%b] from base 2b to integer, yielding
             (2b)(n/b) + (n%b).
          S  Take the sum.
\$\endgroup\$
5
\$\begingroup\$

MATL, 13 bytes

tZl:W&\5ME*+s

Try it at MATL Online! Or verify all test cases.

Explanation

Consider input 12 as an example.

t     % Implicit input. Duplicate
      % STACK: 12, 12
Zl    % Binary logarithm
      % STACK: 12, 3.584962500721156
:     % Range (rounds down)
      % STACK: 12, [1 2 3]
W     % Power with base 2, element-wise
      % STACK: 12, [2 4 8]
&\    % 2-output modulus, element-wise: pushes remainders and quotients
      % STACK: [0 0 4], [6 3 1]
5M    % Push array of powers of 2, again
      % STACK: [0 0 4], [6 3 1], [2 4 8]
E     % Multiply by 2
      % STACK: [0 0 4], [6 3 1], [4 8 16]
*     % Multiply, element-wise
      % STACK: [0 0 4], [24 24 16]
+     % Add, element-wise
      % STACK: [24 24 20]
s     % Sum of array. Implicit display
      % STACK: 68
\$\endgroup\$
4
\$\begingroup\$

C,  58  56 bytes

Thanks to @Dennis for saving two bytes!

s,k;f(n){for(s=0,k=2;k<=n;k*=2)s+=n/k*k*2+n%k;return s;}

Try it online!

C (gcc), 50 bytes

s,k;f(n){for(s=0,k=2;k<=n;)s+=n%k+n/k*(k+=k);k=s;}

Returning by k=s; is undefined behaviour, but works with gcc when optimizations are disabled. Also, n%k+n/k*(k+=k) has unspecified behaviour, but seems to work fine with gcc.

Try it online!

\$\endgroup\$
  • \$\begingroup\$ s,k;f(n){for(s=0,k=2;k<=n;)s+=n%k+n/k*(k*=2);return s;} (55 bytes) \$\endgroup\$ – Kevin Cruijssen Jan 29 '18 at 16:09
  • 1
    \$\begingroup\$ There's no telling which one gets evaluated first n%k or n/k*(k*=2). \$\endgroup\$ – Steadybox Jan 29 '18 at 16:12
  • 1
    \$\begingroup\$ @KevinCruijssen Which side is evaluated first is left unspecified. C is like that... \$\endgroup\$ – Steadybox Jan 29 '18 at 16:17
  • 2
    \$\begingroup\$ Ah, I see you've added that in your answer indeed. Didn't knew this kind of undefined behavior happened in C. I have like three hours experience in C, so I barely know anything about it. TIL :) In Java for(s=0,k=2;k<=n;)s+=n%k+n/k*(k*=2);return s; is completely fine, and n%k will always be evaluated before n/k*(k*=2) and n/k will also evaluate before k*=2. Thanks for the explanation. (I will delete some of my comments now to reduce the clutter.) \$\endgroup\$ – Kevin Cruijssen Jan 29 '18 at 16:18
  • \$\begingroup\$ I love using UB as a feature. And code golfing in a real life language should be in another category anyway :) \$\endgroup\$ – Regis Portalez Jan 30 '18 at 21:34
4
\$\begingroup\$

Jelly, 9 8 bytes

BḊḄÐƤạḤS

Try it online!

B                        to binary          42 -> 1 0 1 0 1 0
 Ḋ                       drop first                 0 1 0 1 0
  ḄÐƤ                    each suffix to decimal   10 10 2 2 0
      Ḥ                  double the input                  84
     ạ                   absolute difference   74 74 82 82 84
       S                 add them up                      396

Vice versa, B¹ƤṖ+BḄS: get prefixes, drop last, add them to input, and sum.

\$\endgroup\$
4
\$\begingroup\$

J, 20 15 14 bytes

+/@}:@:+[\&.#:

Try it online.

15 bytes

1#.-,+:-#.\.@#:

Try it online!

     +:             Input×2
       -            Subtract
        #.\.@#:     The list of binary suffixes of input (in decimal)
   -,               Append negative input
1#.                 Add them up
\$\endgroup\$
  • \$\begingroup\$ why does the double minus formula work? why is it equivalent to dilutions? \$\endgroup\$ – Jonah Jan 30 '18 at 4:06
  • 1
    \$\begingroup\$ @Jonah dilution is adding a certain binary prefix (number "rounded down") to the number, which is equivalent to adding the whole number to itself (both prefix and the remainder) and then subtracting the remainder. \$\endgroup\$ – FrownyFrog Jan 30 '18 at 10:08
4
\$\begingroup\$

Japt, 12 11 bytes

¢¬£¢iYTÃÅxÍ

Try it


Explanation

                 :Implicit input of integer U
¢                :Convert to base-2 string
 ¬               :Split to an array of individual characters/digits
  £    Ã         :Map over the elements, with Y being the current 0-based index
   ¢             :  Convert U to a base-2 string
    iYT          :  Insert a 0 in that string at index Y
        Å        :Slice off the first element of the array
          Í      :Convert each element to a base-10 integer
         x       :Reduce by addition
\$\endgroup\$
3
\$\begingroup\$

JavaScript (ES6), 41 40 bytes

Saved 1 byte thanks to Mr.Xcoder

f=(n,k=1)=>k<n&&(n&k)+2*(n&~k)+f(n,k-~k)

Test cases

f=(n,k=1)=>k<n&&(n&k)+2*(n&~k)+f(n,k-~k)

console.log(f(2  )) //    4
console.log(f(3  )) //    5
console.log(f(7  )) //   24
console.log(f(12 )) //   68
console.log(f(333)) // 5128
console.log(f(512)) // 9216

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

Retina, 53 50 47 bytes

.+
*
+`(_+)\1
$1O
O_
_
L$`\B
$`O$'
+%`\B
¶$`¶
_

Try it online! Link includes test cases. Edit: Saved 3 bytes thanks to @MartinEnder. Explanation:

.+
*
+`(_+)\1
$1O
O_
_

Convert from decimal to binary, but using O to represent 0, as it's not a digit, and _ to represent 1, as it's the default repetition character in Retina 1.

L$`\B
$`O$'

Insert an O between each pair of digits, and collect the results as a list.

+%`\B
¶$`¶

Convert from binary to unary. (This conversion produces extra Os, but we don't care.)

_

Sum and convert to decimal.

\$\endgroup\$
  • \$\begingroup\$ Binary to decimal conversion can be done in 12 bytes (saving 3): tio.run/##K0otycxLNPz/… See this answer for how it works. \$\endgroup\$ – Martin Ender Feb 2 '18 at 18:22
  • \$\begingroup\$ @MartinEnder Thanks, I keep forgetting about that. (I was also slightly disappointed that the alternative version only works on a single number.) \$\endgroup\$ – Neil Feb 3 '18 at 1:24
  • \$\begingroup\$ Well, in the case where you've got each number on its own line you can make it work with an additional %. If it's more complicated you'd need something like /[O_]+/_. \$\endgroup\$ – Martin Ender Feb 3 '18 at 9:17
2
\$\begingroup\$

Pyth, 13 bytes

smiXd.BQZ2Ssl

Try it here!

Explanation

smiXd.BQZ2Ssl | Full program.

           sl | The base-2 logarithm of the input, floored to an integer.
          S   | Create the integer range [1 ... the floored logarithm].
 m            | And map a function over it.
------------+-+-----------------------------------------------------
  iXd.BQZ2  | The function to be mapped (uses a variable d).
     .BQ    | In the binary representation of the input...
   X    Z   | ... Insert a zero...
    d       | ... At index d.
  i      2  | And convert the result from base 2 to an integer.
------------+-+-----------------------------------------------------
s             | Sum the resulting list.
\$\endgroup\$
2
\$\begingroup\$

Jelly, 10 bytes

BµLḤ_J’×µḄ

Try it online!

Not the shortest currently, but it could be if there's a way around Bµ µḄ...

Explanation

BµLḤ_J’×µḄ    Main link. Argument: n (integer)
B             Binary; convert n to an binary of binary digits. Call this A.
 µ            Start a new monadic link with argument A.
  L           Length; yield len(A). We'll call this l.
   Ḥ          Unhalve; yield l * 2.
     J        Length range; yield [1, 2, ..., l].
    _         Subtract; yield [l*2 - 1, l*2 - 2, ..., l].
      ’       Decrement; subtract one from each item.
       ×      Multiply each item by the corresponding item in A. Call this B.
        µ     Start a new monadic link with argument B.
         Ḅ    Unbinary; convert from a binary array to a decimal.

Basically, this works by multiplying each binary digit by a magic number. I can't explain it without visualizing it, so here's the binary number we'll be working with:

1111

As explained by the challenge, he output we want is the sum of these binary numbers:

10111  = 2^4 + 2^2 + 2^1 + 2^0
11011  = 2^4 + 2^3 + 2^1 + 2^0
11101  = 2^4 + 2^3 + 2^2 + 2^0

However, we don't actually have to insert zeroes: Jelly's "unbinary" atom will accept numbers other than just 0 and 1. When we allow ourselves to use 2, this pattern gets simpler:

2111   = 2*2^3 + 1*2^2 + 1*2^1 + 1*2^0
2211   = 2*2^3 + 2*2^2 + 1*2^1 + 1*2^0
2221   = 2*2^3 + 2*2^2 + 2*2^1 + 1*2^0

When we sum up the digits in each column, we get

6543   = 6*2^3 + 5*2^2 + 4*2^1 + 3*2^0 = 48 + 20 + 8 + 3 = 79.

The trick this answer uses is to generate this pattern, and multiply each digit by the corresponding digit in the original to cancel out the necessary columns. 12, for example, would be represented as

 1100
×6543
=6500  = 6*2^3 + 5*2^2 + 0*2^1 + 0*2^0 = 48 + 20 + 0 + 0 = 68.
\$\endgroup\$
1
\$\begingroup\$

Java 8, 55 bytes

n->{int r=0,i=2;for(;i<=n;r+=n%i+n/i*(i*=2));return r;}

Port of Steadybox' C answer, and golfed 3 bytes in the process.

Try it online.

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

Husk, 13 12 bytes

-1 byte thanks to @Mr. Xcoder!

ṁḋ§z·+Θḣotṫḋ

Try it online!

Explanation

ṁḋ§z·+Θḣ(tṫ)ḋ  -- example input: 6
            ḋ  -- convert to binary: [1,1,0]
  §            -- fork argument
        (tṫ)   -- | tail of tails: [[1,0],[0]]
       ḣ       -- | heads: [[1],[1,1],[1,1,0]]
   z           -- and zipWith the following (example with [1,0] [1])
    · Θ        -- | prepend 0 to second argument: [0,1]
     +         -- | concatenate: [1,0,0,1]
               -- : [[1,0,1,0],[1,1,0,0]]
ṁ              -- map the following (example with [1,0,1,0]) and sum
 ḋ             -- | convert from binary: 10
               -- : 22
\$\endgroup\$
1
\$\begingroup\$

05AB1E, 14 bytes

.²LoDŠ‰ø`r·*+O

Try it online!

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

Pip, 21 18 bytes

2*a-a%2**_MS1,#TBa

Try it online!

Explanation

Call our input number a. For each binary index i at which we want to insert a zero, we can calculate the bits left of the insertion point as a // 2**i (where // is integer division and ** is exponentiation), the bits right of the insertion point as a % 2**i, and therefore the diluted integer as 2 * (a // 2**i) * 2**i + (a % 2**i). But (a // 2**i) * 2**i is equal to a - (a % 2**i), and so we can rearrange to a shorter formula: 2 * (a - a % 2**i) + a % 2**i = 2 * a - a % 2**i.

2*a-a%2**_MS1,#TBa
                       a is 1st command-line argument (implicit)
               TBa     Convert a to binary
              #        Length of the binary expansion
            1,         Range from 1 up to (but not including) that number
          MS           Map this function to the range and sum the results:
2*a-a%2**_              The above formula, where _ is the argument of the function
                       The final result is autoprinted
\$\endgroup\$
1
\$\begingroup\$

R, 141 48 bytes

function(n,l=2^(1:log2(n)))sum(n%%l+(n%/%l*2*l))

Try it online!

Either I'm doing something really wrong or R is just terrible at bit manipulation. Porting Luis Mendo's approach is easy, correct, and golfy.

But if you really just want to muck around with bit operations, MickyT suggested the following 105 byter:

function(i)sum(sapply(1:max(which(b<-intToBits(i)>0)),function(x)packBits(head(append(b,F,x),-1),"i")))-i

Try it online!

\$\endgroup\$
  • \$\begingroup\$ Here's a 111 byte one that I'm sure you could take a few more out of. \$\endgroup\$ – MickyT Jan 29 '18 at 18:19
  • \$\begingroup\$ @MickyT Cheers! very nice, although porting an entirely different approach is better! \$\endgroup\$ – Giuseppe Jan 29 '18 at 22:46
1
\$\begingroup\$

Python 3, 92 80 78 bytes

def b(x):x=f'{x:b}';return sum(int(x[:i]+'0'+x[i:],2)for i in range(1,len(x)))

Try It Online

Thanks to Mr.XCoder and ovs for -12 bytes and -2 bytes respectively.

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

Batch, 92 77 bytes

@set/an=2,t=0
:l
@if %1 geq %n% set/at+=%1*2-(%1%%n),n*=2&goto l
@echo %t%

Edit: Switched to the same formula everyone else is using.

\$\endgroup\$
0
\$\begingroup\$

Jelly, 14 bytes

BLḊṬœṗ¥€Bj€0ḄS

Try it online!

\$\endgroup\$
0
\$\begingroup\$

Perl 5, 36 + 1 (-p) = 37 bytes

$\+=$_*2-($_&$.-1)while($.*=2)<=$_}{

Try it online!

\$\endgroup\$
0
\$\begingroup\$

Attache, 57 bytes

Sum##UnBin=>{Join[Join=>_,"0"]}=>SplitAt#1&`:@{#_-1}##Bin

Try it online!

I thought I'd approach the problem from a non-bit manipulation approach, as such an approach is impractical in Attache. I have to investigate some of the parts of this approach for alternatives.

Explanation

Here is an expanded version:

Define[$joinByZero, {Join[Join=>_,"0"]}]

Define[$insertionPoints,
    SplitAt#1&`:@{#_-1}
]

Define[$f,
Sum##UnBin=>joinByZero=>insertionPoints##Bin
]

This simply takes the binary representation of the number, splits it at certain points, inserts zeroes there, converts back to decimal, and sums them together.

\$\endgroup\$
0
\$\begingroup\$

J, 33 bytes

1#.[:}:#.@(<\;@(,0;])"0<@}.\.)@#:

Most probably there is much room for further golfing.

How?

@#: convert to binary and

<@}.\. - find all suffices, drop the first digit from each and box

<\ - find all prefixes and box them

(,0;])"0 - to each prefix append 0 then append the corresponding beheaded suffix

;@ raze (unbox)

1#.[:}:#.@ - convert to decimal, curtail and sum

Try it online!

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