A number theory problem by Prabhav Bansal

Number Theory Level 3

Compute the smallest positive integer $N$ such that $\dfrac{N!} { 12^{12} }$ is an integer.

The answer is 28.

5 solutions

Dev Sharma
Aug 24, 2015

12^12 = 2^24 * 3^12

As n must be a number which should be divisibe by 2^24 and 3^12 And we want smallest number which can be divided by 2^24 and 3^12 So n = 28!

How do you know it's 28 though?

Josh Banister - 5 years, 9 months ago

We need a number that has 12 3s and 24 2s in its prime factorization.

Every multiple of 3 adds one 3, every multiple of 9 adds an additional 3, and a multiple of 27 adds yet another 3. Thus 27! has 9+3+1=13 3s; 26! only has 10 3s. You can just count these 3s up on your fingers if you are being lazy as you count up from 1! to 27!.

Likewise every multiple of 2, 4, 8, 16 adds 1, 2, 3, and 4 2s to the prime factorization respectively. 27! however only has 13 2s, 6 4s, 3 8s, and one 16 - that's only 23 2s. 28 adds an extra 4 to give it 25 2s in the prime factorization.

Jason Short - 5 years, 9 months ago

Hi dev! I've got N=27 as the smallest integer which satisfy the condition of the problem. 27! = 1.08888694504184E+28, 12^12 = 8916100448256, 27!/(12^12) = 1221259171945310 Please correct me if I was wrong.

Rene Dela Cerna - 5 years, 9 months ago

My guess would be that you are hitting a rounding error.

Tony Flury - 5 years, 9 months ago

Yeah it could be 1-of the reasons. another thing which makes me curious about, how can we assure that this Bruce force will give us the smallest integer without seeing its all number digits (applicable for too large #s)?

Rene Dela Cerna - 5 years, 9 months ago

@Rene Dela Cerna – Two techniques spring to mind :

Use a calculator which does completely accurate Big Integers - some modern programming languages have libraries to do, and python does this automatically (and has a very cool interactive console which allows you to do calculations without writing code).
Some techniques like modular arithmetic allows us to work with larger numbers without loss of generality - but to be honest, I prefer technique 1 :-)

Tony Flury - 5 years, 9 months ago

Vincent Miller Moral
Aug 31, 2015

# De Polignac chu chu

from math import factorial as fact

# Brute force
N = 1
while True:
    if fact(N) % (12**12) == 0:
        print N
        break
    N += 1

def depolignac(n, base):
    ans = 0
    i = base
    while i <= n:
        ans += ( n/i )
        i *= base
    return ans

# Semi Brute Force
N = 1
while N:
    pass
    if depolignac(N,2) >= 24 and depolignac(N,3) >= 12:
        print N
        break
    N += 1

Tony Flury
Aug 31, 2015

More brute force from me - python 2

import math
a = 12**12
for i in range(1, 1000):
    if math.factorial(i) % a == 0:
        print i
        break

Akiva Weinberger
Aug 26, 2015

28! has 14+7+3+1=25 factors of 2, and 9+3+1=13 factors of 3, which means it has more than enough 2s and 3s. 27! has 13+6+3+1=23 factors of 2, so it's not sufficient. Thus, 28 is the answer.

Saarthak Marathe
Aug 24, 2015

I used brute force method and got N=28 as 12^12=2^24*3^12

What is brute force method

Chinmayee Behera - 5 years, 9 months ago

It means that you actually calculate the values rather than doing it in a simple way. Sometimes it helps but sometimes it does not and may turn out a very tedious job. In problems like this, it is easy to use this method.

Saarthak Marathe - 5 years, 9 months ago

A number theory problem by Prabhav Bansal

The answer is 28.

5 solutions

0 pending reports