8
\$\begingroup\$

Consider the following table for the function d(n), which calculates the number of factors that n is divisible by without a remainder:

n    | 1 | 2 | 3 | 4 | 5 | 6 | 7 | 8 | 9 | 10 | 11 | 12 | ...
d(n) | 1 | 2 | 2 | 3 | 2 | 4 | 2 | 4 | 3 | 4  | 2  | 6  | ...

Going from left to right, it is possible to determine the "champion" of the current subsequence:

  • The first champion in the sequence [1] is n = 1 with d(1) = 1.
  • The second champion in the next sequence, [1, 2] is n = 2 with d(2) = 2.
  • The sequence [1, 2, 3] has no new champions, because d(3) = d(2) = 2, and 2 earned the title first.
  • The third champion appears the sequence [1, 2, 3, 4]: d(4) = 3, which is greater than the previous champion with d(2) = 2.
  • The next champion is 6 in [1, 2, 3, 4, 5, 6] with d(6) = 4.
  • The next champion is 12 with d(12) = 6.

The champions can be denoted in the table:

n    | 1 | 2 | 3 | 4 | 5 | 6 | 7 | 8 | 9 | 10 | 11 | 12 | ...
d(n) | 1 | 2 | 2 | 3 | 2 | 4 | 2 | 4 | 3 | 4  | 2  | 6  | ...
       x   x       x       x                         x

You task is the following: Write a program that given an integer n, print all champions in the range [1, n] (n inclusive). The output format does not matter (test cases below display array format). Standard code golf rules and scoring applies.

Test cases

1 -> [1]
2 -> [1, 2]
3 -> [1, 2]
4 -> [1, 2, 4]
5 -> [1, 2, 4]
6 -> [1, 2, 4, 6]
7 -> [1, 2, 4, 6]
8 -> [1, 2, 4, 6]
9 -> [1, 2, 4, 6]
10 -> [1, 2, 4, 6]
11 -> [1, 2, 4, 6]
12 -> [1, 2, 4, 6, 12]
24 -> [1, 2, 4, 6, 12, 24]
36 -> [1, 2, 4, 6, 12, 24, 36]

Hint: The output should always be a prefix of the List of Highly Composite Numbers.

\$\endgroup\$
  • \$\begingroup\$ Obligatory OEIS \$\endgroup\$ – FryAmTheEggman Jul 6 '16 at 21:27
  • \$\begingroup\$ Hello, and welcome to PPCG! This is a good challenge, except uoi don't define what a "champion" is. \$\endgroup\$ – NoOneIsHere Jul 6 '16 at 21:27
  • \$\begingroup\$ @NoOneIsHere - The OP does implicitly. "d(3) = d(2) = 2, and 2 earned the title first." and "d(4) = 3, which is greater than the previous champion with d(2) = 2", so a champion must be the next greater d(n) for greater n. (If d(n) > d(n-x) where x > 0, it is a champion) \$\endgroup\$ – owacoder Jul 6 '16 at 21:33
  • \$\begingroup\$ @owacoder: Sorry, I didn't see that. \$\endgroup\$ – NoOneIsHere Jul 6 '16 at 21:33
  • \$\begingroup\$ This is inspired by the new Numberphile video, isn't it? \$\endgroup\$ – LegionMammal978 Jul 6 '16 at 21:38
3
\$\begingroup\$

Jelly, 10 bytes

0rÆDL€»\IT

Try it online!

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

05AB1E, 16 15 bytes

0U>GNÑg©X›i®UN,

Explanation

0U               # initialize the record as 0
  >G             # for each number in 1 to N
    NÑg©         # get number of divisors
        X›i      # if number of divisors is a new record
           ®U    # save new record
             N,  # print the new record holder on a new line

Try it online

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

MATL, 14 13 bytes

0i:t!\~sY>hdf

Try it online!

Explanation

0      % Push 0
i:     % Take input n. Push [1 2 ... n]
t!\    % 2D array of all combinations of modulo between elements of [1 2 ... n]
~s     % Sum of zeros of each column. Gives number of divisors for [1 2 ... n]
Y>     % Cumulative maximum
h      % Concatenate with 0 
d      % Consecutive differences
f      % Indices of nonzero elements. Implicitly display
\$\endgroup\$
  • \$\begingroup\$ Woah! I did not know you could create a 2d matrix like that! That's really cool! Also, you could take 2 bytes off by just pushing a one, instead of joining it, since output format doesn't matter. matl.tryitonline.net/#code=OnQhXH5zWT5kZlEx&input=MzY \$\endgroup\$ – DJMcMayhem Jul 6 '16 at 21:56
  • \$\begingroup\$ @DrGreenEggsandIronMan Yes, I use broadcasting all the time :-) As for the format, I assume the numbers have to be at least sorted \$\endgroup\$ – Luis Mendo Jul 6 '16 at 22:00
  • \$\begingroup\$ Well, OP said The output format does not matter (test cases below display array format). but I suppose it's up to you. \$\endgroup\$ – DJMcMayhem Jul 6 '16 at 22:26

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