Donate to Remove ads

Got a credit card? use our Credit Card & Finance Calculators

Thanks to johnstevens77,Anonymous,MyNameIsUrl,6Tricia,staffordian, for Donating to support the site

Factorials

cinelli
Lemon Slice
Posts: 412
Joined: November 9th, 2016, 11:33 am
Has thanked: 152 times
Been thanked: 103 times

Factorials

#448829

Postby cinelli » October 8th, 2021, 8:55 pm

This puzzle is to find all solutions of

n! * (n-1)! = m!

where m and n are non-negative integers.

Cinelli

NotSure
2 Lemon pips
Posts: 222
Joined: February 5th, 2021, 4:45 pm
Has thanked: 130 times
Been thanked: 61 times

Re: Factorials

#448926

Postby NotSure » October 9th, 2021, 12:47 pm

I am probably just embarrassing myself here, but since m! = m * (m-1)!, then are the only solutions where m! = 1 or (m-1)! = 1, i.e. m = n = 1 or 2?

Gengulphus
Lemon Quarter
Posts: 4215
Joined: November 4th, 2016, 1:17 am
Been thanked: 2536 times

Re: Factorials

#448930

Postby Gengulphus » October 9th, 2021, 1:00 pm

NotSure wrote:I am probably just embarrassing myself here, but since m! = m * (m-1)!, then are the only solutions where m! = 1 or (m-1)! = 1, i.e. m = n = 1 or 2?

No - there's at least one more solution. It's not difficult to find it by just trying out values for n - but the difficulty in the problem is to establish whether there are any more beyond that, and if not, to actually prove that there aren't any more.

Gengulphus

NotSure
2 Lemon pips
Posts: 222
Joined: February 5th, 2021, 4:45 pm
Has thanked: 130 times
Been thanked: 61 times

Re: Factorials

#448931

Postby NotSure » October 9th, 2021, 1:15 pm

NotSure wrote:I am probably just embarrassing myself here, ...
:oops:

Indeed, 7 and 10.

Edit: apologies for not following the puzzle convention regarding answers, even woeful ones. If I am tempted to try any others, will do in future :oops:

UncleEbenezer
Lemon Half
Posts: 7230
Joined: November 4th, 2016, 8:17 pm
Has thanked: 1000 times
Been thanked: 1749 times

Re: Factorials

#449279

Postby UncleEbenezer » October 11th, 2021, 1:25 pm

If Gengulphus hasn't solved it, I infer it's not easy. I wonder if it's not merely not easy, but unsolved/unsolvable?

My thoughts are far from conclusive, but in the spirit of the board I'll wrap them in mild spoiler-protection lest someone start out on the same path and get further than me.

We can trivially reformulate the question in various ways. The one that looks most promising is

(n-1)! = m!/n!

or (n-1)! = (n+1)(n+2)...(m)

Example in the simple case already posted of 7/10, 6! = 8*9*10.

That gives us a constraint: none of (n+1) .. m can be prime. Which in turn raises the question over whether a fully general solution plunges us into the territory of distribution of the primes, which we know to be unsolved.

Or can we do better looking for solutions to N! as a product of consecutive integers starting at N+2?

Can we prove there are no such cases beyond N=6 or some other finite N without resorting to elusive prime properties?
Perhaps for example looking to other formulations - a property of the factors of square factorial numbers in the left side of the OP?

Powers of 2 might do it. 6! divides by 16. 8! by no power of 2 below 128, which pushes candidates for m a long way up. As n grows, powers of 2 in the left side of the OP inevitably grow faster than is feasible on the right.

But that's armwaving.

NotSure
2 Lemon pips
Posts: 222
Joined: February 5th, 2021, 4:45 pm
Has thanked: 130 times
Been thanked: 61 times

Re: Factorials

#449332

Postby NotSure » October 11th, 2021, 4:58 pm

UncleEbenezer wrote:If Gengulphus hasn't solved it, I infer it's not easy. I wonder if it's not merely not easy, but unsolved/unsolvable?


When my research led me to papers by Paul 'another roof, another proof' Erdos, I quickly realised that I was not merely out of my depth, but at the bottom of the Mariana Trench.

modellingman
Lemon Slice
Posts: 379
Joined: November 4th, 2016, 3:46 pm
Has thanked: 160 times
Been thanked: 191 times

Re: Factorials

#449344

Postby modellingman » October 11th, 2021, 5:20 pm

cinelli wrote:This puzzle is to find all solutions of

n! * (n-1)! = m!

where m and n are non-negative integers.

Cinelli


Not really a spoiler but the outcome of a struggle towards what seems to be (to me at least) a reasonable hypothesis



My strong suspicion is for m>10 there are no further solutions.

With a lot of arm-waving my suspicion is founded on the table below.

The table represents the prime factorisation of the integer factorials from 2 to 32 inclusive. The values 2 to 32 appear in the first (header) column of the table, whilst the prime numbers appear in ascending order in the first (header) row of the table. The values in the main body of the table, are the powers of the prime numbers involved in the prime factorisation of the corresponding integer factorial.

For example, take the row labelled with a "6" in column 1. This row contains values of 4, 2 and 1 and indicates that 6! is factorised as
(2^4)*(3^2)*(5^1).


....|  2 |  3 |  5 |  7 | 11 | 13 | 17 | 19 | 23 | 29 | 31 |
----+----+----+----+----+----+----+----+----+----+----+----+----
2 | 1 | | | | | | | | | | |
----+----+----+----+----+----+----+----+----+----+----+----+----
3 | 1 | 1 | | | | | | | | | |
----+----+----+----+----+----+----+----+----+----+----+----+----
4 | 3 | 1 | | | | | | | | | |
----+----+----+----+----+----+----+----+----+----+----+----+----
5 | 3 | 1 | 1 | | | | | | | | |
----+----+----+----+----+----+----+----+----+----+----+----+----
6 | 4 | 2 | 1 | | | | | | | | |
----+----+----+----+----+----+----+----+----+----+----+----+----
7 | 4 | 2 | 1 | 1 | | | | | | | |
----+----+----+----+----+----+----+----+----+----+----+----+----
8 | 7 | 2 | 1 | 1 | | | | | | | |
----+----+----+----+----+----+----+----+----+----+----+----+----
9 | 7 | 4 | 1 | 1 | | | | | | | |
----+----+----+----+----+----+----+----+----+----+----+----+----
10 | 8 | 4 | 2 | 1 | | | | | | | |
----+----+----+----+----+----+----+----+----+----+----+----+----
11 | 8 | 4 | 2 | 1 | 1 | | | | | | |
----+----+----+----+----+----+----+----+----+----+----+----+----
12 | 10 | 5 | 2 | 1 | 1 | | | | | | |
----+----+----+----+----+----+----+----+----+----+----+----+----
13 | 10 | 5 | 2 | 1 | 1 | 1 | | | | | |
----+----+----+----+----+----+----+----+----+----+----+----+----
14 | 11 | 5 | 2 | 2 | 1 | 1 | | | | | |
----+----+----+----+----+----+----+----+----+----+----+----+----
15 | 11 | 6 | 3 | 2 | 1 | 1 | | | | | |
----+----+----+----+----+----+----+----+----+----+----+----+----
16 | 15 | 6 | 3 | 2 | 1 | 1 | | | | | |
----+----+----+----+----+----+----+----+----+----+----+----+----
17 | 15 | 6 | 3 | 2 | 1 | 1 | 1 | | | | |
----+----+----+----+----+----+----+----+----+----+----+----+----
18 | 16 | 8 | 3 | 2 | 1 | 1 | 1 | | | | |
----+----+----+----+----+----+----+----+----+----+----+----+----
19 | 16 | 8 | 3 | 2 | 1 | 1 | 1 | 1 | | | |
----+----+----+----+----+----+----+----+----+----+----+----+----
20 | 18 | 8 | 4 | 2 | 1 | 1 | 1 | 1 | | | |
----+----+----+----+----+----+----+----+----+----+----+----+----
21 | 18 | 9 | 4 | 3 | 1 | 1 | 1 | 1 | | | |
----+----+----+----+----+----+----+----+----+----+----+----+----
22 | 19 | 9 | 4 | 3 | 2 | 1 | 1 | 1 | | | |
----+----+----+----+----+----+----+----+----+----+----+----+----
23 | 19 | 9 | 4 | 3 | 2 | 1 | 1 | 1 | 1 | | |
----+----+----+----+----+----+----+----+----+----+----+----+----
24 | 22 | 10 | 4 | 3 | 2 | 1 | 1 | 1 | 1 | | |
----+----+----+----+----+----+----+----+----+----+----+----+----
25 | 22 | 10 | 6 | 3 | 2 | 1 | 1 | 1 | 1 | | |
----+----+----+----+----+----+----+----+----+----+----+----+----
26 | 23 | 10 | 6 | 3 | 2 | 2 | 1 | 1 | 1 | | |
----+----+----+----+----+----+----+----+----+----+----+----+----
27 | 23 | 13 | 6 | 3 | 2 | 2 | 1 | 1 | 1 | | |
----+----+----+----+----+----+----+----+----+----+----+----+----
28 | 25 | 13 | 6 | 4 | 2 | 2 | 1 | 1 | 1 | | |
----+----+----+----+----+----+----+----+----+----+----+----+----
29 | 25 | 13 | 6 | 4 | 2 | 2 | 1 | 1 | 1 | 1 | |
----+----+----+----+----+----+----+----+----+----+----+----+----
30 | 26 | 14 | 7 | 4 | 2 | 2 | 1 | 1 | 1 | 1 | |
----+----+----+----+----+----+----+----+----+----+----+----+----
31 | 26 | 14 | 7 | 4 | 2 | 2 | 1 | 1 | 1 | 1 | 1 |
----+----+----+----+----+----+----+----+----+----+----+----+----
32 | 31 | 14 | 7 | 4 | 2 | 2 | 1 | 1 | 1 | 1 | 1 |
----+----+----+----+----+----+----+----+----+----+----+----+----
| | | | | | | | | | | |



There are a few properties of the table that are worth noting.

  1. The table is relatively easy to construct. Each row is constructed from the preceding row, by factorising the next digit into its prime factors and adding the powers of the primes in this factorisation to the values in the preceding row. For example the row labelled "9" represents the factorisation of 9! by the numbers: 7, 4, 1 and 1 (representing (2^7)*(3^4)*(5^1)*(7^1)). The next row, involves factoring 10 as (2^1)*(5^1) and adding the powers in this factorisation (both equal to 1) to the corresponding powers from row 9 to yield values of 8 (=7+1),4, 2 (=1+1) and 1 for the subsequent row labelled "10".

  2. The prime factorisation of a general factorial (say k!) involves all the primes up to a maximum prime factor. Using P(i) to denote the i'th prime (starting with P(1)=2) and P(M) to denote the maximum prime factor, then the relationship between M and k is determined by P(M)<=k<P(M+1). Put another way, the M'th prime is the maximum prime factor in the factorisation of k! for all integers k in the range P(M) to P(M+1)-1. I suspect that this relies on my hypothesised (and unproven) general property of prime numbers that P(i)^2 > P(i+1).

  3. The powers of the prime factors are non-increasing across each row and non-decreasing down the columns. The latter occurs because if j>k then k! is a factor of j!. So if P(i)^q is a factor of k! it must also be a factor of j!. The power will increase beyond q in the factorisation of j! if P(i) is a factor of j*(j-1)*...*(k+1). The former arises because, looking down the table, the power associated with a particular prime factor increases whenever the value of k is a multiple of the prime factor - so the power of the prime 2 increases in every second row of the table, that of prime 3 in every 3rd row, that of 5 in every fifth row, etc. For a given value of k, a smaller prime will have been increased more often than a larger prime, so its power in the prime factorisation of k! will be greater than that of the larger one. I suspect use of Legendre's formula might add a bit more rigour here.

  4. The power of the maximum prime factor is always 1. This is a corollary of 2., above.

  5. The number of distinct prime factors in the prime factorisation of k! increases by at most 1 when compared to the prime factorisation of (k-1)!. In visual terms, the number of non-zero values in a row of the table is never more than 1 greater than the number in the preceding row. The number of distinct prime factors in the factorisation of k! increases if and only if k is a prime number.

Consider now n! = m! * (m -1)!

The maximum prime factor of n! (say P(M), with its power of 1 in the factorisation - see 4., above) must also be involved in the factorisation of m!*(m-1)!

However, it can only be involved in the factorisation of one of m! and (m-1)!, otherwise if P(M) is involved in the factorisation of both m! and (m-1)! this implies a power of 2 for P(M) in the factorisation of n! (a contradiction) and, if involved in neither, a power of 0 (again a contradiction). The non-decreasing property of powers down a column means the contradiction can only be resolved if P(M) is a factor of m! but not of (m-1)!

It also follows from 2., above that m = P(M). Since m is the first integer divisible by P(M). It also follows from 5., that the maximum prime factor of (m-1)! is P(M-1).

Now
n! = m! * (m-1)!
= m * [(m-1)!^2]
= P(M) * [(m-1)!^2]

(m-1)! has a maximum prime factor of P(M-1). Because of the squaring of (m-1)!, the final two terms of the factorisation of n! implied by the final equation will be P(M-1)^2 and P(M)^1

So (after some far from rigorous argument) a necessary condition for n! = m! * (m-1)! is that the factorisation of n! has a 1 and 2 as the powers of its largest and next largest prime factors.

Looking at the table only two rows meet this condition: the rows labelled 6 and 10. 10! does satisfy the solution (spotted by NotSure), 6! does not - though it gets close since 6! = 5!*3! - so the condition is clearly not sufficient.

There is a clear trend evident in the table that the number of trailing 1's in each row has a tendency to increase, implying the the necessary condition of a 2 and 1 in the final two positions will not be met as the number of rows is increased.


Lootman
The full Lemon
Posts: 11247
Joined: November 4th, 2016, 3:58 pm
Has thanked: 144 times
Been thanked: 2493 times

Re: Factorials

#449346

Postby Lootman » October 11th, 2021, 5:41 pm

NotSure wrote:When my research led me to papers by Paul 'another roof, another proof' Erdos, I quickly realised that I was not merely out of my depth, but at the bottom of the Mariana Trench.

Perhaps you should be grateful. Paul Erdos had a life of tragedy and was dead by the age of 33.

The smartest kid at my school was a child prodigy at maths. He had his A level in pure maths by age 15 and, since he could not go up to Trinity College, Cambridge for another 2/3 years on grounds of age, did a B.Sc. in maths in his spare time at school just for something to do. I believe he had a Ph.D by the time he was 21. He self reported his IQ as 182 and the guy was incapable of lying so I can believe it.

He was also the most socially awkward kid I ever knew, with zero social skills. He was dead at age 26, suicide I heard. I guess the world was just too stupid for him.

malkymoo
Lemon Slice
Posts: 318
Joined: November 23rd, 2016, 9:45 am
Has thanked: 20 times
Been thanked: 83 times

Re: Factorials

#449393

Postby malkymoo » October 11th, 2021, 8:32 pm

Lootman wrote:Perhaps you should be grateful. Paul Erdos had a life of tragedy and was dead by the age of 33.



Not according to accounts I have read. His Wikipedia profile says he died at 83.

NotSure
2 Lemon pips
Posts: 222
Joined: February 5th, 2021, 4:45 pm
Has thanked: 130 times
Been thanked: 61 times

Re: Factorials

#449394

Postby NotSure » October 11th, 2021, 8:35 pm

Lootman wrote:
NotSure wrote:When my research led me to papers by Paul 'another roof, another proof' Erdos, I quickly realised that I was not merely out of my depth, but at the bottom of the Mariana Trench.

Perhaps you should be grateful. Paul Erdos had a life of tragedy and was dead by the age of 33.

The smartest kid at my school was a child prodigy at maths. He had his A level in pure maths by age 15 and, since he could not go up to Trinity College, Cambridge for another 2/3 years on grounds of age, did a B.Sc. in maths in his spare time at school just for something to do. I believe he had a Ph.D by the time he was 21. He self reported his IQ as 182 and the guy was incapable of lying so I can believe it.

He was also the most socially awkward kid I ever knew, with zero social skills. He was dead at age 26, suicide I heard. I guess the world was just too stupid for him.


Erdos lived to the ripe old age of 83 but was, by all accounts, quite eccentric. He too obtained a PhD at 21. The problem above can (IMHO) be framed as combinatorics, so if anyone could crack it, I suspect he could. It seems many exceptional mathematicians have done their best work by their mid 20's. It sounds like the prodigy you knew had little else to fall back on. A sad story.

Lootman
The full Lemon
Posts: 11247
Joined: November 4th, 2016, 3:58 pm
Has thanked: 144 times
Been thanked: 2493 times

Re: Factorials

#449396

Postby Lootman » October 11th, 2021, 8:45 pm

NotSure wrote:
Lootman wrote:
NotSure wrote:When my research led me to papers by Paul 'another roof, another proof' Erdos, I quickly realised that I was not merely out of my depth, but at the bottom of the Mariana Trench.

Perhaps you should be grateful. Paul Erdos had a life of tragedy and was dead by the age of 33.

The smartest kid at my school was a child prodigy at maths. He had his A level in pure maths by age 15 and, since he could not go up to Trinity College, Cambridge for another 2/3 years on grounds of age, did a B.Sc. in maths in his spare time at school just for something to do. I believe he had a Ph.D by the time he was 21. He self reported his IQ as 182 and the guy was incapable of lying so I can believe it.

He was also the most socially awkward kid I ever knew, with zero social skills. He was dead at age 26, suicide I heard. I guess the world was just too stupid for him.

Erdos lived to the ripe old age of 83 but was, by all accounts, quite eccentric. He too obtained a PhD at 21. The problem above can (IMHO) be framed as combinatorics, so if anyone could crack it, I suspect he could. It seems many exceptional mathematicians have done their best work by their mid 20's. It sounds like the prodigy you knew had little else to fall back on. A sad story.

Child prodigies in maths are common. I could speculate that is because maths is really a closed system that tells you nothing about the universe, so you do not need experience to be good at it. Mathematical truths are true by convention rather than by induction. A priori rather than a posteriori. So they can appeal to those with fierce logical skills but little awareness of the real world. That in turn enables children to become mathematical geniuses, but to no avail. In real life they can fail especially as they get older and lose their edge. Bobby Fischer on steroids.

The boy genius i cited earlier had a father at Oxford who taught nihilism as a coherent philosophy. That might explain a few things!

Gengulphus
Lemon Quarter
Posts: 4215
Joined: November 4th, 2016, 1:17 am
Been thanked: 2536 times

Re: Factorials

#450840

Postby Gengulphus » October 17th, 2021, 5:44 pm

UncleEbenezer wrote:If Gengulphus hasn't solved it, I infer it's not easy. I wonder if it's not merely not easy, but unsolved/unsolvable?

As a mathematical problem in number theory, it is actually quite an easy consequence of known results - it could probably be written up in mathematical paper form as a single-page paper, even including all the standard parts of such a paper (e.g. title, author name and affiliation, synopsis, references) provided one kept those parts succinct. I had the bare bones of such a "mathematicians' solution" quite quickly (which wasn't all that different from what you and modellingman have come up with between you).

But I was looking for a "puzzlers' solution", and I think that should be something that only uses known mathematical results if they are quite widely known by non-mathematicians as well as mathematicians. So (for example) Pythagoras's theorem is fine in a "puzzler's solution", but Stirling's approximation (a form of which might actually be quite useful for this problem, though that's not a possibility I've explored) is not.

I haven't found such a "puzzler's solution", but I have found a hybrid solution whose "puzzlers' solution" part may be of interest, and whose "mathematicians' solution" part is one of the many known results which indicate that "the territory of distribution of the primes, which we know to be unsolved" is rather misleading - it's true that there are aspects of the distribution of the primes that are unsolved, but there are a lot of known results about it. So here's that solution, spoiler-protected:

Let the number of times the prime 2 divides r! be e2(r), so that 2^e2(r) divides r! but 2^(e2(r)+1) does not. Clearly we can calculate the values of e2(r) iteratively by starting with e2(0) = 0, and then successively calculating e2(1) as e2(0) plus the number of times 2 divides 1 (which is 0), e2(2) as e2(1) plus the number of times 2 divides 2 (which is 1), e2(3) as e2(2) plus the number of times 2 divides 3 (which is 0), e2(4) as e2(3) plus the number of times 2 divides 4 (which is 2), etc, and in general e2(r+1) as e2(r) plus the number of times that 2 divides r+1.

There is however a shortcut formula to calculate e2(r) without that long chain of calculating successive values working one step at a time up from 1 to r:

e2(r) = r - setbits(r)

where setbits(r) is the number of 1s in the binary representation of r.

To prove that, note first that it's true for r=0, since the binary representation of 0 is 0, which contains no 1s, and so the formula says that e2(0) = 0 - setbits(0) = 0-0 = 0, which is true.

Now assume that e2(r) = r - setbits(r) for a particular value of r. The procedure to get from the binary representation of r to the binary representation of r+1 is to work upwards from the lowest bit, successively converting all 1s we encounter to 0s, until we encounter a 0 (if r is a power of 2 minus 1, so that its binary representation is all 1s, that means the implicit 0 beyond its left end), convert that 0 to a 1 and stop. So compared with the number of 1s in the binary representation of r, the number of 1s in the binary representation of r+1 is reduced by the number of 1s at the bottom of the binary representation of r and then increased by 1, i.e.:

setbits(r+1) = setbits(r) - (number of 1s at the bottom of the binary representation of r) + 1

But that process also says that the number of 1s at the bottom of the binary representation of r is equal to the number of 0s at the bottom of the binary representation of r+1, and that's equal to the number of times that 2 divides r+1, so:

setbits(r+1) = setbits(r) - (number of times 2 divides r+1) + 1

So:

(r+1) - setbits(r+1) = (r+1) - setbits(r) + (number of times 2 divides r+1) - 1

= r - setbits(r) + (number of times 2 divides r+1), by cancelling out the +1 and -1

= e2(r) + (number of times 2 divides r+1), using the assumption we've made about e2(r)

= e2(r+1), using the step-by-step formula for calculating e2(r)

So we know that the formula is correct for r=0, and that if it's correct for a particular value of r, it's also correct for the next value of r. So it's correct for r=1, and hence for r=2, and hence for r=3, and so on ad infinitum. I.e. e2(r) = r - setbits(r) is true for all positive integer values of r.

Now let's take a look at the actual problem, of finding all integer solutions of n!*(n-1)! = m! Counting factors of 2 on both sides, that tells us that:

e2(n) + e2(n-1) = e2(m)

which on substituting e2(r) = r - setbits(r) for each of r = n-1, n, m and rearranging produces:

2n - m = setbits(n) + setbits(n-1) + 1 - setbits(m)

If n is a b-bit number, i.e. if 2^(b-1) <= n <= 2^b-1, then we know that setbits(n) <= b, setbits(n-1) <= b-1 and setbits(m) >= 1, so:

2n - m <= b + (b-1) + 1 - 1 = 2b-1

Now return to n!*(n-1)! = m!, and assume that (n-1)! is not 1 (if it is, n must be 1 or 2, leading quickly and easily to the two solutions (n,m) = (1,1) and (2,2), and to no others). Divide through by n!, to get:

1 * 2 * 3 * ... * (n-1) = (n+1) * (n+2) * (n+3) * ... * m

Every factor on the right hand side is greater than all factors on the left hand side, all of those factors are positive integers, and there is at least one factor on the right hand side. If the number of factors on the right hand side were greater than or equal to the number of factors on the left hand side, that would imply that the product of the right hand side is greater than the product of the left hand side, which isn't compatible with them being equal. So there are fewer factors on the right hand side than on the left hand side, and since there are n-1 factors on the left hand side and m-n on the right, we can deduce that m-n < n-1, or rearranging, that 1 < 2n-m.

So we've got 1 < 2n-m <= 2b-1 - which informally means that m is less than twice n, but by an amount that is essentially only a small multiple of the logarithm of n, so that as n gets larger, it becomes small compared with the difference between m and n. That gives me a way of solving it by appealing to known mathematical results, by observing that if any of n+1, n+2, ..., m is prime, we cannot have equality between the left hand side and the right hand side, because the left hand side isn't divisible by that prime and the right hand side is. That brought Bertrand's Postulate (which is actually a theorem - Bertrand conjectured the result, Chebyshev proved it) to mind, which says that for all n>1, there is a prime p with n < p < 2n. That cannot be applied directly to this problem, since we've shown that m is less than 2n. But as the link indicates, there are known tighter results, such as that for n>1, there is always a prime between 3n and 4n (see the link's reference 6 for a paper proving this - but if you don't understand the proof, I won't try to explain it on TLF, both because TLF's facilities for posting mathematical equations are totally inadequate and because I would need to spend quite a bit of time studying the paper to understand it myself!).

Supposing as above that n is a b-bit number, we've already got 2n-m <= 2b-1, or equivalently m >= 2n-(2b-1). Dividing through by n, that gives us m/n = 2 - (2b-1)/n >= 2 - (2b-1)/2^(b-1) since n being a b-bit number implies that n >= 2^(b-1).

If b = 6, that gives us m/n >= 2 - 11/32 = 1.65625, so m >= 1.65625n. That means that the highest multiple of 4 in the n+1 to m range is at least 1.65625n - 3, so 3/4 of that highest multiple of 4 is at least 0.75*(1.65625n-3) = 1.2421875n - 2.25 = n + (0.2421875n - 2.25), and since n >= 32, that's at least n + (0.2421875*32 - 2.25) = n + 5.5 > n+1. So we've got a multiple of 4 in the n+1 to m range such that the corresponding multiple of 3 is also in the n+1 to m range, which the tighter result described above says is enough to show that there is a prime in that range - a prime that doesn't divide n! or (n-1)!, but does divide m!, showing that n!*(n-1)! is not equal to m!

The same argument can be seen to also work for b = 7, 8, 9, etc, just with different and more relaxed constants - e.g. when b = 7, we get m >= (2 - 13/64)n = 1.796875n, making a (multiple of 3, corresponding multiple of 4) pair even easier to fit into the n+1 to m range.

So the binary representation of n has to have at most 5 bits, i.e. n <= 31. It's now just a case of looking at the 31 possibilities (n=0 not being a possibility because (n-1)! would be (-1)!, which isn't defined (even if you use the extended definition of factorials in terms of the gamma function, as gamma(0) also isn't defined):

n   b  lower limit for  primes p definitely in
m (= 2n-(2b-1)) n+1 <= p <= m range
==============================================
1 1 1 none
2 2 1 none
3 2 3 none
4 3 3 none
5 3 5 none
6 3 7 7
7 3 9 none
8 4 9 none
9 4 11 11
10 4 13 11,13
11 4 15 13
12 4 17 13,17
13 4 19 17,19
14 4 21 17,19
15 4 23 17,19,23
16 5 23 17,19,23
17 5 25 19,23
18 5 27 19,23
19 5 29 23,29
20 5 31 23,29,31
21 5 33 23,29,31
22 5 35 23,29,31
23 5 37 29,31,37
24 5 39 29,31,37
25 5 41 29,31,37,41
26 5 43 29,31,37,41,43
27 5 45 29,31,37,41,43
28 5 47 29,31,37,41,43,47
29 5 49 31,37,41,43,47
30 5 51 31,37,41,43,47
31 5 53 37,41,43,47,53

If there are any primes in the last column, n!*(n-1)! is not divisible by them and m! is, so n!*(n-1)! and m! cannot be equal. So we only need to test n!*(n-1)! for being a factorial for n = 1, 2, 3, 4, 5, 7 and 8, and that shows that (n,m) = (1,1), (2,2) and (7,10) are the only solutions.

Gengulphus


Return to “Games, Puzzles and Riddles”

Who is online

Users browsing this forum: No registered users and 1 guest