18
\$\begingroup\$

Background

The sequence in the title is A245788 "n times the number of 1's in the binary expansion of n" ("times" here means multiplication), which starts like this:

1,   2,   6,   4,   10,  12,  21,  8,   18,  20,
33,  24,  39,  42,  60,  16,  34,  36,  57,  40,
63,  66,  92,  48,  75,  78,  108, 84,  116, 120,
155, 32,  66,  68,  105, 72,  111, 114, 156, 80,
123, 126, 172, 132, 180, 184, 235, 96,  147, 150,
204, 156, 212, 216, 275, 168, 228, 232, 295, 240, ...

Though it is not immediately obvious, this sequence has some duplicates (same number appearing at least twice). The first duplicate appears at \$a(22) = a(33) = 66\$. The next ones are \$a(39) = a(52) = 156\$, and \$a(44) = a(66) = 132\$. Note that the duplicates do not appear in ascending order.

It is easy to prove that there exist infinitely many duplicates in this sequence, and I suspect that there exist infinitely many \$k\$-plicates (the numbers that appear at least \$k\$ times in the sequence) as well. For the record, the first triplicate entry is \$a(1236) = a(1545) = a(2060) = 6180\$.

Challenge

Produce the sequence of unique duplicates in A245788, in ascending order. For example, 156 should appear after 132, and 6180 should appear only once in the sequence. The following is the list of all 124 terms under 10000, generated using this Python program:

66,   132,  156,  228,  264,  300,  312,  420,  435,  456,
528,  588,  600,  624,  804,  840,  870,  912,  1056, 1100,
1164, 1176, 1200, 1220, 1248, 1545, 1572, 1608, 1635, 1680,
1740, 1824, 2050, 2100, 2112, 2196, 2200, 2244, 2316, 2328,
2340, 2352, 2400, 2440, 2496, 2580, 2628, 2820, 3090, 3108,
3140, 3144, 3216, 3270, 3325, 3360, 3480, 3535, 3648, 3690,
4025, 4098, 4100, 4200, 4224, 4260, 4392, 4400, 4488, 4620,
4632, 4656, 4680, 4704, 4800, 4880, 4914, 4992, 5160, 5256,
5640, 5880, 6125, 6180, 6195, 6216, 6280, 6288, 6432, 6510,
6540, 6650, 6660, 6720, 6960, 7070, 7296, 7380, 7608, 8040,
8050, 8196, 8200, 8220, 8292, 8400, 8448, 8490, 8520, 8580,
8784, 8800, 8976, 9228, 9240, 9264, 9312, 9360, 9408, 9600,
9732, 9760, 9828, 9984

Default I/O methods for are allowed:

  • Take no input, and output the terms infinitely.
  • Take \$n\$ as input, and output the \$n\$-th term (0- or 1-indexed).
  • Take \$n\$ as input, and output the first \$n\$ terms.

Standard rules apply. The shortest code in bytes wins.

\$\endgroup\$

13 Answers 13

13
\$\begingroup\$

JavaScript (V8),  72 71 70  69 bytes

A full program that prints the sequence forever.

for(n=1;c=2;c||print(n))for(d=++n;d--;)c>>=n==(h=n=>n&&h(n&n-1)+d)(d)

Try it online!

Commented

for(                   // infinite outer loop:
  n = 1;               //   start with n = 1
  c = 2;               //   before each iteration: initialize c to 2
  c || print(n)        //   after each iteration: print n if c = 0
)                      //
  for(                 //   inner loop:
    d = ++n;           //     increment n and start with d = n
    d--;               //     stop when d = 0 / decrement d
  )                    //
    c >>=              //     right-shift d by 1 position if ...
      n == (           //       ... n is equal to ...
        h = n =>       //       ... the result of the recursive function h
          n &&         //       which adds d as many times as there are
          h(n & n - 1) //       bits set in d, using n & n - 1 to clear
          + d          //       the least significant bit at each iteration
      )(d)             //

Note

We decrement \$d\$ right away in the inner loop, which means that we never consider the case where the divisor of \$n\$ is \$n\$ itself. But that would only work if there's a single 1 in the binary representation of \$n\$, which means that \$n\$ is a power of \$2\$ and all its divisors have a single 1 in their binary representation as well. Therefore, \$n=1\times n\$ is the only possible solution and \$n\$ does not belong to the sequence.

\$\endgroup\$
2
  • 3
    \$\begingroup\$ 66: for(d=o=[];;o[d]&&print(d))o[p=(h=n=>n&&h(n&n-1)+d)(++d)]=o[p]+1|0 \$\endgroup\$ – tsh Apr 23 at 5:31
  • 1
    \$\begingroup\$ @tsh Nice. I think this is different enough to be posted as a separate answer. \$\endgroup\$ – Arnauld Apr 23 at 10:20
7
\$\begingroup\$

Jelly, 9 bytes

×BS)ċ>1µ#

Try it online!

-1 byte thanks to Jonathan Allan

Explanation

×BS)ċ>1µ#  Main Link
        #  nfind; find first (read from stdin) numbers such that
     >1    there is more than one
    ċ      occurrence of the original number in the list of
   )       each number from 1 to N
×BS        multiplied by its hamming weight

Note that ×BS doesn't actually chain as × (B S). In other words, this isn't actually multiplying each number by its hamming weight. However, by distribution of multiplication over addition, instead of doing \$a\times(b_1+b_2+\dots+b_n)\$, it's actually doing \$ab_1+ab_2+\dots+ab_n\$ because × vectorizes, and those happen to be literally the same thing. It chains as (× B) S, but that ends up giving the same result.

\$\endgroup\$
2
  • \$\begingroup\$ Save one replacing Ɗ€ with ) TIO. \$\endgroup\$ – Jonathan Allan Apr 23 at 17:48
  • \$\begingroup\$ @JonathanAllan Totally forgot that existed. Thanks! \$\endgroup\$ – hyper-neutrino Apr 23 at 17:53
6
\$\begingroup\$

Scala, 144 135 bytes

Saved 9 bytes thanks to Kirill L.!

n=>Stream.from(1).scanLeft(0::Nil)((s,x)=>x*Integer.bitCount(x)::s).collect{case h::t if t toSet h=>h}.distinct.take(n*2).sorted take n

Try it in Scastie!

Pretty naive solution. Returns the first n elements.

n =>  //How many elements you want
Stream.from(1)  //Infinite list of natural numbers
.scanLeft(0::Nil) //Scan left, collecting prefixes of hamming number sequence (reversed)
((s,x) =>    //s is the previous sequence, x is a natural number
  x * Integer.bitCount(x)  //Find the next hamming number
    ::s)   //Prepend to s
.collect{  //Keep the ones that work with this PartialFunction:
  case h::t  //A prefix with hamming number h at the start and initial piece t
    if t toSet h =>  //If h is a duplicate
    h        //Keep h
}.distinct  //Uniquify
.take(n*2)  //Take the first 2n elements
.sorted    //Sort them
take n    //Take the first n elements
\$\endgroup\$
2
  • 2
    \$\begingroup\$ You can save a few bytes by using Java interop for bitCount. I had to use fully qualified class name to make it work, but I don't know Scala, so maybe it can be shortened somehow. \$\endgroup\$ – Kirill L. Apr 23 at 16:42
  • \$\begingroup\$ @KirillL. Thanks! I made it work with Integer, which is imported by default, although java.lang.Long clashes with scala.Long \$\endgroup\$ – user Apr 23 at 17:23
3
\$\begingroup\$

Pyth, 19 15 bytes

.f<1lfq*TsjT2ZS

Try it online!

Outputs the first \$n\$ elements of the sequence.

Explanation:

.f<1lfq*TsjT2ZS   | Full program
.f<1lfq*TsjT2ZSZQ | with implicit variables
------------------+--------------------------------------------------
.f              Q | first Q (input) numbers Z starting at 1 such that
    lf        SZ  |  the number of elements T of [1, Z] such that
       *TsjT2     |   T * sum of digits of T in base 2
      q      Z    |   equals Z
  <1              |  is greater than 1
\$\endgroup\$
3
\$\begingroup\$

Haskell, 65 bytes

[x|x<-[1..],sum[1|n<-[1..x],n*h!!(n-1)==x]>1]
h=1:do x<-h;[x,x+1]

Try it online!

The list defined in the first line is the infinite list of duplicates in the sequence. h is a helper infinite list that contains the hamming weight of \$n\$ at position \$n-1\$.

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

Charcoal, 29 bytes

≔⁰θFN«≦⊕θW›²LΦθ⁼θ×λΣ⍘λ²≦⊕θ»Iθ

Try it online! Link is to verbose version of code. Outputs the nth element of the sequence. Explanation:

≔⁰θ

Start the accumulator at 0.

FN«

Find n elements of the sequence.

≦⊕θ

Increment the accumulator.

W›²LΦθ⁼θ×λΣ⍘λ²

While the number of integers whose base 2 sum multiple equals the accumulator is less than 2, ...

≦⊕θ

... increment the accumulator.

»Iθ

Output the accumulator.

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

JavaScript (V8), 66 bytes

for(d=o=[];;o[d]&&print(d))o[p=(h=n=>n&&h(n&n-1)+d)(++d)]=o[p]+1|0

Try it online!

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

Ruby, 55 bytes

loop{p$.if(1..$.+=1).count{|y|y*y.digits(2).sum==$.}>1}

Try it online!

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

Red, 140 136 bytes

func[n][i: m: 1 until[d: 0 repeat k i: i + 1[p: k b: 0
until[b: p % 2 * k + b(p: p / 2)= 0]if b = i[d: d + 1]]if d > 1[m: m + 1]n < m]i]

Try it online!

Returns the \$n\$th element of the sequence.

Since the above code is really slow, I decided to write a faster function:

Faster alternative, 168 bytes

func[n][r:[]m: copy#()i: 0 until[p: i: i + 1 b: 0
until[b: p % 2 * i + b(p: to 1 p / 2)= 0]either m/:b[r:
union r to[]b][m/:b: 1](length? r)=(2 * n)]take/part sort r n]

Try it online!

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

R, 78 76 bytes

Edit: -2 bytes thanks to Kirill L.

repeat{T=T+1;s=0;for(n in 1:T)s=s+(n*sum(n%/%2^(0:n)%%2)==T);if(s>1)show(T)}

Try it online!

\$\endgroup\$
1
  • \$\begingroup\$ @KirillL. - Thanks! Somehow I was sure I'd tried repeat + for, or something similar, but obviously didn't get it right... \$\endgroup\$ – Dominic van Essen Apr 23 at 15:25
2
\$\begingroup\$

Clojure, 81 78 bytes

#(for[i(range):when(second(for[j(range i):when(=(*(Long/bitCount j)j)i)]j))]i)

Try it online!

Returns the infinite sequence.

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

Japt, 18 16 bytes

Èò_*¤è1Ãè¥X z}jU

Try it

Thanks to @Galen Ivanov for spotting an error which once fixed saved me 1 Byte!

È ... }jU  - first input U elements to return a truthy value when passed trough : f(XYZ)
ò_   >  range[0..X] trough f(Z)
*      * multiply Z by
¤è1à   * convert to binary string an count '1's
è¥X  > is number of elements == X
z    > divided by 2 not 0 ?
\$\endgroup\$
2
  • \$\begingroup\$ I think your solution doesn't list 6180 - can you check? \$\endgroup\$ – Galen Ivanov Apr 23 at 10:33
  • 1
    \$\begingroup\$ Yes @Galen Ivanov I thought I had to output only doubled while 6180 is triple, thanks! \$\endgroup\$ – AZTECCO Apr 23 at 11:16
0
\$\begingroup\$

05AB1E, 12 bytes

∞ʒLDb1ö*y¢2@

Outputs the infinite sequence.

Try it online.

Explanation:

∞            # Push an infinite positive list: [1,2,3,...]
 ʒ           # Filter each value `y` by:
  L          #  Pop and create a list in the range [1,`y`]
   D         #  Duplicate this list
    b        #  Convert each inner value to a binary-String
     1ö      #  Sum the digits of each inner binary-String (by converting it to base-1)
       *     #  Multiply each binary-sum to its [1,`y`] value of the duplicated list
        y¢   #  Count how many times `y` occurs in this list
          2@ #  And check whether this count is larger than or equal to 2
             # (after which the filtered infinite list is output implicitly as result)
\$\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.