#PROBLEM LINK:

Author: Suthirth V

Tester: Suthirth V

Editorialist: Suthirth V

#DIFFICULTY:

Simple

#PREREQUISITES:

Radical - The radical of n, rad(n), is the product of distinct prime factors of n. For example, 504 = 23 x 32 x 7, so rad(504) = 2 x 3 x 7 = 42.

Sieve of Eratosthenes - Python Implementation

#PROBLEM:

Elon Musk has trained **N** ensembles of neural networks, each given an index from 1 to **N**, to power a self-replicating robot. Owing to the complexities in interstellar travel, he has space for only one ensemble. Empirically, he finds that the combined intelligence **I** of the n^{th} ensemble is given by the following equation:

**I**(n) = Product of the prime factors of n

For example, the intelligence of the 18^{th} ensemble is given by:

**I**(18) = 2*3 = 6

Given **N**, help Elon find the index of the ensemble with the maximum intelligence.

(Hint: Brute force will not work for large **N**. Efficiency of the algorithm is crucial for the survival of the self-replicating bots in deep space.)

#QUICK EXPLANATION:

Compute the radicals by sieving all the numbers and sort them to get the index of the highest radical.

#EXPLANATION:

Let’s define the sieving function which computes the radicals for **N** numbers.

```
def compute(N):
## initialize the list of radicals
rads = [1]*(N+1)
## loop through the entire list starting from 2
for i in xrange(2,len(rads)):
if rads[i] == 1:
## instead of switching True/False for prime/not-prime in the original sieve,
## multiply the prime factors iteratively to get the radical in the end.
for j in xrange(i,len(rads),i):
rads[j] = rads[j] * i
# once the radicals are generated, sort the list to get the highest radical
data = [(rads[i],i) for i in xrange(len(rads))]
data.sort()
return data[N][1]
```

Here is a sample of the iterative updates happening to compute the radicals for **N**=30 for every iteration of *i*

```
compute(30)
[1, 1, 2, 1, 2, 1, 2, 1, 2, 1, 2, 1, 2, 1, 2, 1, 2, 1, 2, 1, 2, 1, 2, 1, 2, 1, 2, 1, 2, 1, 2]
[1, 1, 2, 3, 2, 1, 6, 1, 2, 3, 2, 1, 6, 1, 2, 3, 2, 1, 6, 1, 2, 3, 2, 1, 6, 1, 2, 3, 2, 1, 6]
[1, 1, 2, 3, 2, 1, 6, 1, 2, 3, 2, 1, 6, 1, 2, 3, 2, 1, 6, 1, 2, 3, 2, 1, 6, 1, 2, 3, 2, 1, 6]
[1, 1, 2, 3, 2, 5, 6, 1, 2, 3, 10, 1, 6, 1, 2, 15, 2, 1, 6, 1, 10, 3, 2, 1, 6, 5, 2, 3, 2, 1, 30]
[1, 1, 2, 3, 2, 5, 6, 1, 2, 3, 10, 1, 6, 1, 2, 15, 2, 1, 6, 1, 10, 3, 2, 1, 6, 5, 2, 3, 2, 1, 30]
[1, 1, 2, 3, 2, 5, 6, 7, 2, 3, 10, 1, 6, 1, 14, 15, 2, 1, 6, 1, 10, 21, 2, 1, 6, 5, 2, 3, 14, 1, 30]
[1, 1, 2, 3, 2, 5, 6, 7, 2, 3, 10, 1, 6, 1, 14, 15, 2, 1, 6, 1, 10, 21, 2, 1, 6, 5, 2, 3, 14, 1, 30]
[1, 1, 2, 3, 2, 5, 6, 7, 2, 3, 10, 1, 6, 1, 14, 15, 2, 1, 6, 1, 10, 21, 2, 1, 6, 5, 2, 3, 14, 1, 30]
[1, 1, 2, 3, 2, 5, 6, 7, 2, 3, 10, 1, 6, 1, 14, 15, 2, 1, 6, 1, 10, 21, 2, 1, 6, 5, 2, 3, 14, 1, 30]
[1, 1, 2, 3, 2, 5, 6, 7, 2, 3, 10, 11, 6, 1, 14, 15, 2, 1, 6, 1, 10, 21, 22, 1, 6, 5, 2, 3, 14, 1, 30]
[1, 1, 2, 3, 2, 5, 6, 7, 2, 3, 10, 11, 6, 1, 14, 15, 2, 1, 6, 1, 10, 21, 22, 1, 6, 5, 2, 3, 14, 1, 30]
[1, 1, 2, 3, 2, 5, 6, 7, 2, 3, 10, 11, 6, 13, 14, 15, 2, 1, 6, 1, 10, 21, 22, 1, 6, 5, 26, 3, 14, 1, 30]
[1, 1, 2, 3, 2, 5, 6, 7, 2, 3, 10, 11, 6, 13, 14, 15, 2, 1, 6, 1, 10, 21, 22, 1, 6, 5, 26, 3, 14, 1, 30]
[1, 1, 2, 3, 2, 5, 6, 7, 2, 3, 10, 11, 6, 13, 14, 15, 2, 1, 6, 1, 10, 21, 22, 1, 6, 5, 26, 3, 14, 1, 30]
[1, 1, 2, 3, 2, 5, 6, 7, 2, 3, 10, 11, 6, 13, 14, 15, 2, 1, 6, 1, 10, 21, 22, 1, 6, 5, 26, 3, 14, 1, 30]
[1, 1, 2, 3, 2, 5, 6, 7, 2, 3, 10, 11, 6, 13, 14, 15, 2, 17, 6, 1, 10, 21, 22, 1, 6, 5, 26, 3, 14, 1, 30]
[1, 1, 2, 3, 2, 5, 6, 7, 2, 3, 10, 11, 6, 13, 14, 15, 2, 17, 6, 1, 10, 21, 22, 1, 6, 5, 26, 3, 14, 1, 30]
[1, 1, 2, 3, 2, 5, 6, 7, 2, 3, 10, 11, 6, 13, 14, 15, 2, 17, 6, 19, 10, 21, 22, 1, 6, 5, 26, 3, 14, 1, 30]
[1, 1, 2, 3, 2, 5, 6, 7, 2, 3, 10, 11, 6, 13, 14, 15, 2, 17, 6, 19, 10, 21, 22, 1, 6, 5, 26, 3, 14, 1, 30]
[1, 1, 2, 3, 2, 5, 6, 7, 2, 3, 10, 11, 6, 13, 14, 15, 2, 17, 6, 19, 10, 21, 22, 1, 6, 5, 26, 3, 14, 1, 30]
[1, 1, 2, 3, 2, 5, 6, 7, 2, 3, 10, 11, 6, 13, 14, 15, 2, 17, 6, 19, 10, 21, 22, 1, 6, 5, 26, 3, 14, 1, 30]
[1, 1, 2, 3, 2, 5, 6, 7, 2, 3, 10, 11, 6, 13, 14, 15, 2, 17, 6, 19, 10, 21, 22, 23, 6, 5, 26, 3, 14, 1, 30]
[1, 1, 2, 3, 2, 5, 6, 7, 2, 3, 10, 11, 6, 13, 14, 15, 2, 17, 6, 19, 10, 21, 22, 23, 6, 5, 26, 3, 14, 1, 30]
[1, 1, 2, 3, 2, 5, 6, 7, 2, 3, 10, 11, 6, 13, 14, 15, 2, 17, 6, 19, 10, 21, 22, 23, 6, 5, 26, 3, 14, 1, 30]
[1, 1, 2, 3, 2, 5, 6, 7, 2, 3, 10, 11, 6, 13, 14, 15, 2, 17, 6, 19, 10, 21, 22, 23, 6, 5, 26, 3, 14, 1, 30]
[1, 1, 2, 3, 2, 5, 6, 7, 2, 3, 10, 11, 6, 13, 14, 15, 2, 17, 6, 19, 10, 21, 22, 23, 6, 5, 26, 3, 14, 1, 30]
[1, 1, 2, 3, 2, 5, 6, 7, 2, 3, 10, 11, 6, 13, 14, 15, 2, 17, 6, 19, 10, 21, 22, 23, 6, 5, 26, 3, 14, 1, 30]
[1, 1, 2, 3, 2, 5, 6, 7, 2, 3, 10, 11, 6, 13, 14, 15, 2, 17, 6, 19, 10, 21, 22, 23, 6, 5, 26, 3, 14, 29, 30]
[1, 1, 2, 3, 2, 5, 6, 7, 2, 3, 10, 11, 6, 13, 14, 15, 2, 17, 6, 19, 10, 21, 22, 23, 6, 5, 26, 3, 14, 29, 30]
```

#ALTERNATIVE SOLUTION:

The other approach would be to brute force it

#AUTHOR’S AND TESTER’S SOLUTIONS:

Author’s solution can be found here