Highly composite numbers
Jelly, 15 bytes
,®ÆDL€ṛ©0>/?µƓ#
For input n, this prints the first n highly composite numbers.
For n = 20, it takes less than two seconds on Try it online!
How it works
,®ÆDL€ṛ©0>/?µƓ# Main link. No implicit input.
µ Push the chain to the left on the local link stack.
Ɠ Read an integer n from STDIN.
# Execute the chain for k = 0, 1, 2, ..., until it returned a truthy
value n times. Return the list of matches.
,® Pair k with the value in the register (initially 0).
ÆD Compute the divisors of k and the register value.
L€ Count both lists of divisors.
? If
>/ k has more divisors than the register value:
ṛ© Save k in the register and return k.
0 Else: Return 0.
Alternate version, 13 bytes (non-competing)
While the below code worked in the latest version of Jelly that precedes this challenge, the implementation of M
was very slow, and it did not comply with the time limit. This has been fixed.
ÆDL®;©MḢ’>µƓ#
Try it online!
How it works
ÆDL®;©MḢ’>µƓ# Main link. No implicit input.
µ Push the chain to the left on the local link stack.
Ɠ Read an integer n from STDIN.
# Execute the chain for k = 0, 1, 2, ..., until it returned a truthy
value n times. Return the list of matches.
ÆD Compute the divisors of k.
L Count them.
®; Append the count to the list in the register (initially 0 / [0]).
© Save the updated list in the register.
M Obtain all indices the correspond to maximal elements.
Ḣ Retrieve the first result.
’> Subtract 1 and compare with k.
This essentially checks if the first maximal index is k + 2, where
the "plus 2" accounts for two leading zeroes (initial value of the
register and result for k = 0).
05AB1E, 15 14 bytes
The input in zero-indexed. That means that n = 0
gives 1
, n = 1
gives 2
, etc. Code:
$µ>DÑgD®›i©¼}\
Explanation:
$ # Pushes 1 and input
µ # Counting loop, executes until the counting variable is equal to input
> # Increment (n + 1)
DÑ # Duplicate and calculate all divisors
gD # Get the length of the array and duplicate
® # Retrieve element, standardized to zero
›i } # If greater than, do...
© # Copy value into the register
¼ # Increment on the counting variable
\ # Pop the last element in the stack
Calculates n = 19, which should give 7560
in about 10 seconds.
Try it online!
Uses CP-1252 encoding.
MATL, 26 24 bytes
~XKx`K@@:\~s<?@5MXKx]NG<
Try it online!
The current largest number of divisors found is kept in clipboard K. Highly composite numbers (HCN) are kept directly on the stack. A loop keeps testing candidates to HCN. When one is found it is left on the stack, and clipboard K is updated. The loop exits when the desired number of HCN have been found.
~ % take input implicitly (gets stored in clipboard G). Transform into a 0
% by means of logical negation
XKx % copy that 0 into clipboard K, and delete
` % do...while
K % push largest number of divisors found up to now
@ % push iteration index, i: current candidate to HCN
@: % range [1,...,i]
\ % modulo operation
~s % number of zeros. This is the number of divisors of current candidate
< % is it larger than previous largest number of divisors?
? % if so: a new HCN has been found
@ % push that number
5M % push the number of divisors that was found
XKx % update clipboard K, and delete
] % end if
N % number of elements in stack
G< % is it less than input? This the loop condition: exit when false
% end do...while implicitly
% display all numbers implicitly