Duplicates in "n × hamming weight of n" sequence

Question

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 sequence 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 code-golf rules apply. The shortest code in bytes wins.

Answer 1

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.

Answer 2

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.

Answer 3

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

Answer 4

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

Answer 5

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

Answer 6

Charcoal, 29 bytes

≔⁰θＦＮ«≦⊕θＷ›²ＬΦθ⁼θ×λΣ⍘λ²≦⊕θ»Ｉθ

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

≔⁰θ

Start the accumulator at 0.

ＦＮ«

Find n elements of the sequence.

≦⊕θ

Increment the accumulator.

Ｗ›²ＬΦθ⁼θ×λΣ⍘λ²

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

≦⊕θ

... increment the accumulator.

»Ｉθ

Output the accumulator.

Answer 7

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!

Answer 8

Ruby, 55 bytes

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

Try it online!

Answer 9

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!

Answer 10

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!

Answer 11

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.

Answer 12

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 ?

Answer 13

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)