Problem #383

Squarefree Factorisations
Public 03/03/17 8xp Programming 75.0%

Let's n an integer with the following factorisation : $ n = a_1^{e_1} \times a_2^{e_2} \times \dots \times a_p^{e_p} $ where $a_i$ are squarefree and $ \forall i \in \{1,\dots, p-1 \}\quad a_i \textrm{ divides }a_{i+1}$

For instance :
$ 56 = 2^2 \times 14^1 $
$ 5040 = 2^2 \times 6^1 \times 210^1 $
$ 526773121875 = 3^2 \times 15^3 \times 1155^1 \times 15015^1 $

It can be proved that this factorisation is unique.

For such a factorisation, let's consider all the divisors of n : $ a_1^{f_1} \times a_2^{f_2} \times \dots a_p^{f_p}\textrm{ where }0 \le f_i \le e_i$

Define $ \sigma^\prime(n) = \sum\limits_{d}(d) $ where d runs over the divisors of n as defined above
$\sigma^\prime(5040) = 1 + 2 + 4 + 6 + 12 + 24 + 210 + 420 + 840 + 1260 + 2520 + 5040 = 10339 $

We say that n is a champion if the ratio $ \frac{\sigma^\prime(n)}{n}$ is greater than any ratio $ \frac{\sigma^\prime(m)}{m}$ with $ m \lt n$

Here are the first 10 champions:
$ 1 \centerdot 1 \Rightarrow 2$
$ 2 \centerdot 24 \Rightarrow 2,04166666666667$
$ 3 \centerdot 48 \Rightarrow 2,1875$
$ 4 \centerdot 96 \Rightarrow 2,26041666666667$
$ 5 \centerdot 192 \Rightarrow 2,296875$
$ 6 \centerdot 384 \Rightarrow 2,3151041$6666667
$ 7 \centerdot 768 \Rightarrow 2,32421875$
$ 8 \centerdot 1152 \Rightarrow 2,3515625$
$ 9 \centerdot 2304 \Rightarrow 2,37022569444444$
$10 \centerdot 4608 \Rightarrow 2,37955729166667$

What is the $66^{th}$ champion?

[My timing: 5 sec]



You need to be a member to keep track of your progress.
Register


Time may end, but hope will last forever.

Other Challenge Sites

Contact

elasolova
[64][103][109][97][105][108][46][99][111][109]