Thread: One VERY CHALLENGING QUESTION (no-one has been able to work this one out yet!)

1. One VERY CHALLENGING QUESTION - STILL UNANSWERED, despite the 9 replies!!!

The question, as an image, can be seen below:

I have asked many mathematicians about this, and so far, an easy way of working this one out has not been found. I would be extremely grateful to anyone who could explain how to work this question out. Good luck!

2. Originally Posted by yeah:)
The question, as an image, can be seen below:

I have asked many mathematicians about this, and so far, an easy way of working this one out has not been found. I would be extremely grateful to anyone who could explain how to work this question out. Good luck!
Every number can be written as product of prime factors.

$\displaystyle 1000000 = 2^6 \cdot 5^6$.

So I suppose you have 2x2x2x2x2x2x5x5x5x5x5x5.

Then just split that up into 3 groups of numbers...

Such as 2x2x2 2x2x2 and 5x5x5x5x5x5.

Or 2x2, 2x2x2x2x5x5, 5x5x5x5

Cant remember the exact formula to figure out how many of those there are though! Binomial stuff...

--EDITED FOR FAIL--

Plato is good at this sort of thing. So come on in and post up a solution Plato!

EDIT: HAHAHA speak of the devil guess who was looking at this thread when I had finished posting this.

3. Bleh scratch that binomial part.

I think the number of non-unique ways is the solution to...

x + y + z = 12.

With x,y,z > 0 and are integers.

4. Basically you are just forming three groups from twelve numbers (the prime factors of one million). I think Deadstar got the right idea but the answer is not given by this formula.

You first choose a first group of $\displaystyle n$ numbers, $\displaystyle 0 < n < 11$, so the number of combinations is $\displaystyle \binom{12}{n}$.

Then you choose another group of $\displaystyle k$ numbers, $\displaystyle 0 < k < 11 - n$, so the number of combinations is $\displaystyle \binom{12}{k}$.

Finally you are left with a last group of $\displaystyle 12 - n - k$ numbers, so the last number of combinations is $\displaystyle \binom{12}{12 - n - k}$.

So, the number of ways of writing it is :

$\displaystyle \binom{12}{n} \times \binom{12}{k} \times \binom{12}{12 - n - k}$

With $\displaystyle 0 < n < 11$ and $\displaystyle 0 < k < 11 - n$.

Unless there is a way of combining those binomials, I guess a quick exhaustive search through the 132 or so possibilities for $\displaystyle n$ and $\displaystyle k$ should get the answer.

Unless I got it wrong of course ! Don't hesitate to tell me, I'm really unsure about this.

5. Originally Posted by Bacterius
Basically you are just forming three groups from twelve numbers. I think Deadstar got the right idea but the answer is not given by this formula.

You first choose a first group of $\displaystyle n$ numbers, $\displaystyle 0 < n < 11$, so the number of combinations is $\displaystyle \binom{12}{n}$.

Then you choose another group of [tex]k[tex] numbers, $\displaystyle 0 < k < 11 - n$, so the number of combinations is $\displaystyle \binom{12}{k}$.

Finally you are left with a last group of $\displaystyle 12 - n - k$ numbers, so the last number of combinations is $\displaystyle \binom{12}{12 - n - k}$.

So, the number of ways of writing it is :

$\displaystyle \binom{12}{n} \times \binom{12}{k} \times \binom{12}{12 - n - k}$

With $\displaystyle 0 < n < 11$ and $\displaystyle 0 < k < 11 - n$.

Unless there is a way of combining those binomials, I guess a quick exhaustive search through the 132 or so possibilities for $\displaystyle n$ and $\displaystyle k$ should get the answer.

Unless I got it wrong of course ! Don't hesitate to tell me, I'm really unsure about this.
Think that's probably on the right lines. But I think that's non-unique solutions.

I.e. all the ways with 2x2x2 and 2x2x2 would appear in that.

I think it can be solved easier with the post that I put up while (I presume) you were typing your reply. But again, nonunique solutions.

Also, holy hell you're only 16! Smart kid...

6. Yeah I was thinking that nonunique solutions were going to break down my reasoning, I'm going to look at your second solution Deadstar.

Also, holy hell you're only 16! Smart kid...
Thanks

7. Originally Posted by Bacterius
Yeah I was thinking that nonunique solutions were going to break down my reasoning, I'm going to look at your second solution Deadstar.

Thanks
WOW! Thank you so much for your replies!!! All your solutions here seem so complicated to me, though!!! Is there any way of solving the problem that is shorter, or at least, could someone explain this to me in slightly more simple terms? Also, what is the actual final answer?

8. Originally Posted by Bacterius
Yeah I was thinking that nonunique solutions were going to break down my reasoning, I'm going to look at your second solution Deadstar.

Thanks
Ya You should be able to see what I'm getting it but basically x,y,z are the size of the groups of numbers.

So 2x2 2x2x2 $\displaystyle 2x5^6$ would have x=2, y=3, z=7...

9. Originally Posted by yeah:)
WOW! Thank you so much for your replies!!! All your solutions here seem so complicated to me, though!!! Is there any way of solving the problem that is shorter, or at least, could someone explain this to me in slightly more simple terms? Also, what is the actual final answer?
We don't know yet lol...

But solving $\displaystyle x+y+z=12$ gives...

$\displaystyle x+y+z = 9$ for $\displaystyle x,y,x>0$

$\displaystyle = {9+3-1 \choose 9} = {11 \choose 9} = 55$ which seems way too low...

We don't know yet lol...

But solving $\displaystyle x+y+z=12$ gives...

$\displaystyle x+y+z = 9$ for $\displaystyle x,y,x>0$

$\displaystyle = {9+3-1 \choose 9} = {11 \choose 9} = 55$ which seems way too low...
I see... 55 does seem rather low...hopefully, someone can eventually lead this thread to a solution!

11. We know those factors are the product of $\displaystyle 2^s 5^t$ .

Let $\displaystyle 1000000 = 10^6 = xyz$ and $\displaystyle p,q,r$ be the maximum degrees of $\displaystyle 2$ or $\displaystyle 5$ of $\displaystyle x,y,z$ respectively .

We should have $\displaystyle p+q+r = 6$

We have three cases :

CaseI : three of them are distinct and the possible combinations are :

$\displaystyle 6 = 0+1+5 = 0+2+4 = 1+2+3$ so there are three possible combinations in this case .

CaseII : $\displaystyle p=q$ we have

$\displaystyle 6 = 0+0+6 = 1+1+4 = 3+3+0$ also three combinations .

CaseIII : $\displaystyle p=q=r$ which leads to only one possibility : $\displaystyle 6 = 2+2+2$

I use $\displaystyle \binom{a~b~c}{A~B~C}$ to denote the degrees and if two are in the same column , we will write $\displaystyle 10^6$ as $\displaystyle (2^a 5^A) (2^b 5^B )( 2^c 5^C )$ three factors .

Suppose $\displaystyle (a,b,c)~ (A,B,C)$ are distinct

$\displaystyle \binom{a~b~c}{A~B~C}$ has $\displaystyle 3! = 6$ permutations so we should have $\displaystyle 3! \times 3 \times 3 = 54$ counts .

$\displaystyle \binom{a~b~c}{A~A~C}$ has $\displaystyle 3!/2 = 3$ permutations but since it is not convertable we should count $\displaystyle 3 \times 3 \times 3 \times 2 = 54$

$\displaystyle \binom{a~a~c}{A~A~C}$ we could count $\displaystyle 2 \times 3 \times 3 = 18$

$\displaystyle \binom{a~a~a}{A~B~C}$ we have $\displaystyle 1\times 1 \times 3 \times 2 = 6$

$\displaystyle \binom{a~a~a}{A~A~C}$ we have $\displaystyle 1\times 1 \times 3 \times 2 = 6$

$\displaystyle \binom{a~a~a}{A~A~A}$ we have $\displaystyle 1$

Therefore , we have totally $\displaystyle 54+54+18+6+6+1 = 139$ possible ways to write but we have to limit the factors to be greater than one so let's first count how many combinations there are :

Actually , that number is equal to the number of the different positive factors not exceeding $\displaystyle \sqrt{10^6} = 1000$ which is $\displaystyle \frac{ 7\times 7 + 1}{2} = 25$

The answer should be $\displaystyle 139 - 25 = 114$

12. I have confirmed simplependulum's answer using brute force methods.

Code:
(2, 2, 250000)
(2, 4, 125000)
(2, 5, 100000)
(2, 8, 62500)
(2, 10, 50000)
(2, 16, 31250)
(2, 20, 25000)
(2, 25, 20000)
(2, 32, 15625)
(2, 40, 12500)
(2, 50, 10000)
(2, 80, 6250)
(2, 100, 5000)
(2, 125, 4000)
(2, 160, 3125)
(2, 200, 2500)
(2, 250, 2000)
(2, 400, 1250)
(2, 500, 1000)
(2, 625, 800)
(4, 4, 62500)
(4, 5, 50000)
(4, 8, 31250)
(4, 10, 25000)
(4, 16, 15625)
(4, 20, 12500)
(4, 25, 10000)
(4, 40, 6250)
(4, 50, 5000)
(4, 80, 3125)
(4, 100, 2500)
(4, 125, 2000)
(4, 200, 1250)
(4, 250, 1000)
(4, 400, 625)
(4, 500, 500)
(5, 5, 40000)
(5, 8, 25000)
(5, 10, 20000)
(5, 16, 12500)
(5, 20, 10000)
(5, 25, 8000)
(5, 32, 6250)
(5, 40, 5000)
(5, 50, 4000)
(5, 64, 3125)
(5, 80, 2500)
(5, 100, 2000)
(5, 125, 1600)
(5, 160, 1250)
(5, 200, 1000)
(5, 250, 800)
(5, 320, 625)
(5, 400, 500)
(8, 8, 15625)
(8, 10, 12500)
(8, 20, 6250)
(8, 25, 5000)
(8, 40, 3125)
(8, 50, 2500)
(8, 100, 1250)
(8, 125, 1000)
(8, 200, 625)
(8, 250, 500)
(10, 10, 10000)
(10, 16, 6250)
(10, 20, 5000)
(10, 25, 4000)
(10, 32, 3125)
(10, 40, 2500)
(10, 50, 2000)
(10, 80, 1250)
(10, 100, 1000)
(10, 125, 800)
(10, 160, 625)
(10, 200, 500)
(10, 250, 400)
(16, 20, 3125)
(16, 25, 2500)
(16, 50, 1250)
(16, 100, 625)
(16, 125, 500)
(16, 250, 250)
(20, 20, 2500)
(20, 25, 2000)
(20, 40, 1250)
(20, 50, 1000)
(20, 80, 625)
(20, 100, 500)
(20, 125, 400)
(20, 200, 250)
(25, 25, 1600)
(25, 32, 1250)
(25, 40, 1000)
(25, 50, 800)
(25, 64, 625)
(25, 80, 500)
(25, 100, 400)
(25, 125, 320)
(25, 160, 250)
(25, 200, 200)
(32, 50, 625)
(32, 125, 250)
(40, 40, 625)
(40, 50, 500)
(40, 100, 250)
(40, 125, 200)
(50, 50, 400)
(50, 80, 250)
(50, 100, 200)
(50, 125, 160)
(64, 125, 125)
(80, 100, 125)
(100, 100, 100)

114 ways found.

13. Our mathematical mind is finally at peace

14. Thanks undefined ,

I was afraid if the answer is wrong , all the steps i wrote will be thrown to the rubbish bin ... but how did you confirm this ? using your computer ? not using hands , right ?

15. Originally Posted by simplependulum
Thanks undefined ,

I was afraid if the answer is wrong , the steps i wrote will be thrown to rubbish bin ... but how did you confirm this ? using your computer ? not using hands , right ?
Yep, using a computer. The code is a bit of a hodge-podge because I re-used old code for integer factorisation (using a smallest prime sieve algorithm). It was easier to re-use code, even though a method to get the factors of 10^6 wouldn't take many lines. After getting the factors, I just used three nested loops. No need to optimise with such small numbers.

Code:
import java.util.ArrayList;
import java.util.Collections;

public class ProdThreeFactors {

static int L1 = 1000001;
static int[] smallestP = new int[L1]; // smallest prime factor

public static void init() {
for (int i = 2; i < L1; i++)
if (smallestP[i] == 0) {
smallestP[i] = i;
for (int j = i + i; j < L1; j += i)
if (smallestP[j] == 0) smallestP[j] = i;
}
}

public static void main(String[] args) {
long time = System.currentTimeMillis();
int count = 0;
init();
ArrayList<Integer> facts = getFacts(1000000);
for (int i = 1; i < facts.size(); i++)
for (int j = i; j < facts.size(); j++)
for (int k = j; k < facts.size(); k++) {
long d1 = facts.get(i);
long d2 = facts.get(j);
long d3 = facts.get(k);
if (d1*d2 < 1000000 && d1*d2*d3 == 1000000) {
System.out.println("(" + d1 + ", " + d2 + ", " + d3 + ")");
count++;
}
}
System.out.println("\n" + count + " ways found.");
System.out.println("Elapsed: " + (System.currentTimeMillis() - time) / 1000.0 + " s");
}

public static ArrayList<Integer> getFacts(int n) {
// returns list of factors of n in ascending order.
ArrayList<Integer> ret = getFactors(n);
Collections.sort(ret);
return ret;
}

public static ArrayList<Integer> getFactors(int n) {
// returns list of factors of n, not necessarily in ascending order.
if (n >= L1) {
System.out.println("Error: smallest prime sieve limit exceeded.");
return null;
}
ArrayList<Integer> ret = new ArrayList<Integer>();
if (n == 1) {
return ret;
}
ArrayList<Integer> primeFactors = canonicalise(factorise(n));
getFactorsHelper(0, ret, primeFactors, 1);
return ret;
}

public static void getFactorsHelper(int ind, ArrayList<Integer> factors,
ArrayList<Integer> primeFactors, int prod) {
if (ind == primeFactors.size()) {
return;
}
int currPrime = primeFactors.get(ind), currPrimePow = 1;
int multiplicity = primeFactors.get(ind + 1);
for (int i = 0; i <= multiplicity; i++) {
getFactorsHelper(ind + 2, factors, primeFactors, prod * currPrimePow);
currPrimePow *= currPrime;
}
}

public static ArrayList<Integer> canonicalise(ArrayList<Integer> pFacts) {
// input is list of prime factors with duplicates allowed, not necessarily in
// ascending order.
// output is an even-sized list of primes p_i each followed by exponent a_i in
// ascending order.
// composition of functions is useful for factoring n = n_1 * n_2 * ... * n_r where
// the n_i are known, to ease combining of lists for the n_i.
if (pFacts == null || pFacts.isEmpty()) return pFacts;
ArrayList<Integer> canon = new ArrayList<Integer>();
Collections.sort(pFacts);
while (!pFacts.isEmpty()) {
int currPrime = pFacts.remove(0);
int multiplicity = 1;
while (pFacts.size() > 0 && pFacts.get(0).equals(currPrime)) {
pFacts.remove(0);
multiplicity++;
}
}
return canon;
}

public static ArrayList<Integer> factorise(int n) {
// output is list of prime factors in ascending order, duplicates allowed.
if (n < 1) return null;
if (n < 2) return new ArrayList<Integer>();
if (n >= L1) {
System.out.println("Error: smallest prime sieve limit exceeded.");
return null;
}
ArrayList<Integer> factors = new ArrayList<Integer>();
int p = smallestP[n];
n /= p;
while (n % p == 0) {
n /= p;
}
if (n == 1) return factors;
}