There’s an old puzzle popular among a certain type of schoolchildren that challenges the solver to write as many positive integers as possible using exactly four 4’s, together with some set of mathematical operations. (As is often the case with school children, the exact rules tend to get negotiated in real time as the puzzle is being solved.) Some examples are:
But when I became a man, I put away childish things. So here’s the grown-up version of the problem, which I got from Mel Hochster over 20 years ago, and still don’t know how to solve:
This being a grown-up problem, the rules are carefully specified:
The only allowable operations are “square root”, “factorial”, and “floor”. (The floor of a number is its integer part, so that, for example, the floor of 11.2371 is 11.) In fact, you’ve got to do all the factorials first, then all the square roots, then the floor. So for example:
By varying the number of factorials and the number of square roots, can you get every positive integer this way?
Edited to add: When the first seven comments were posted, I had the arithmetic wrong in the examples. It’s fixed now.
I always preffered doing this with the year. e.g.
2+0+1^2=1
2+0*1*2=2
2+0+1^2=3
etc etc usually I try to not use sqrt until I have to and then try not using floor until I have to.
Onto this puzzle I’m not sure I believe the examples you posted.
e.g. for 2 you have trunc(sqrt(4!!))=trunc(sqrt(24!))=trunc(sqrt(6*10^23)=787685471323
unless I am missing something with ou notation. (btw for 2 sqrt(4) or trunc(sqrt(4)) works).
I believe I convinced myself that you could in principle to this if you didn’t need to use those 3 symbols in order. i.e. if
trunc(sqrt(trunc(sqrt(4!!!)))) was allowed.
As long as you don’t need to use all the operations, I can do the one that comes after 3. Then 2 = sqrt4, which is simpler than the solution above.
Looking closer, I don’t understand. (4!)! is very nearly the same as avagadro’s number – 6x 10^23. What is 4!!? Apologies for hopeless math.
! is factorial, !! is factorial of the result. Harold may be confused because I think Steve is. 4!! = 24! = a very big number, and the square root of a very big number is much bigger than 2, and the floor of that is bigger than 2.
Indeed, that is what I got. What is the factorial of a non whole number?
@Harold
Euler’s Gamma function—
http://mathworld.wolfram.com/GammaFunction.html
—is usually used to give the “factorial” of a number that isn’t a positive integer.
The double factorial. It’s not what you think. Here’s more information on the extensions to the factorial.
@Ken: Veto. The rules are clear. ‘The only allowable operations are “square root”, “factorial”, and “floor”. ‘ Your John Roberts imitation is disallowed.
As several have pointed out, I got the arithmetic wrong in the examples. It’s fixed now.
Ken B,
Except the definition of the double factorial and other extensions are well defined. Not so much with the John Roberts tax.
@Ken:
This problem of Steve’s, construct any number with just one four, is isomorphic to the well known Roberts Problem in Con Law: justify any law on the basis of just one tax clause. Nobody knows if it is possible, but no known counter-examples exist.
So I have a heuristic., which says every number “should” be doable. It’s not a proof by any stretch but maybe someone can fill in the gaps.
Consider the collection of half open sets I_1=[2,4),I_2=[4,16),I_3=[16,256), etc etc where each interval is of the form [n,n^2) and we partition [2,infinity). Now start with some mind numbingly large number B (like say 4!!!!!!!. Now start taking successive square roots of B. (that is sqrt(B), sqrt(sqrt(b)), sqrt (sqrt,sqrt(B))) etc) we get exactly 1 element of each I_k.
Now IF we where picking random uber huge and not particularly dense numbers (as oppossed to deterministic 4!!!!!!!!!!! numbers) then we’d hit one of these intervals randomly every time (not uniform random but random). The result of this would be that every interval within a given I_k would eventually get hit and hence every integer would get hit. The issue now is determining why 4!!!!!!!!!!!! is close enough to random in this sense (or why there deterministic nature stops them from rehitting the same intervals time and again).
Jonathan Kariv: I like this heuristic very much.
Steve,
How are you defining k!! ? Is it according the definitions at the links in my comments or are you defining k!! to be (k!)! ?
@Jonathan Kariv: That’s really good.
4(!^n)! will have every prime less than than 4(!^n) as a divisor and primes are ‘notoriously random’ so maybe that suggests something.
Ken: 4!! means (4!)!
I wouldn’t characterize the four fours problem as childish (unless you were being sarcastic? Given your love of math I think this might be the case). I’m sure the likes of Martin Gardner would have found them to be quite interesting.
Consider the examples offered by Landsburg: To generate the number 4, we need to use one factorial and one square root. To generate the number 5, we need two factorials but five square roots. Does this pattern hold? That is, does the ratio of square roots to factorials continue to grow as we seek larger and larger integers?
4 seems a bit easier to represent with one 4 than you make it to be. I’d try the following simple solution: 4
Genius!
@nobody.really Well the more factorials you have the more sqrt/factorial you’ll need for numbers of approimately fixed size. 4!! is about 6*(10^23) 4!!! will have about 10^23 digits (being rough here) so to get anything below a mllion (under 6 digits) we’d need something like a hundered square roots. The number of sqrts we’d need to get anything below a milion from 4!!!! is something I don’t even want to think about.
Seeing as 4(!^n) only gives 1 answer in each I_k (comment 11) we’re going tohave to start using more factorials (and proportionally more sqrts) very quickly. Then we will eventually actually bump into 4!!! which we can make with absolutely no sqrt symbols
I love this puzzle! I saw it many years ago, with the number 3 instead of 4, but I haven’t been able to find the original website for many years.
I believe every positive integer can be obtained in an infinite number of different ways.
let f(a,b) be the sqrt function applied a times to the factorial function applied b times to 4.
Now, log(f(a,b)) is log(4!..!)/2^a
So, log_2(log(f(a,b))) is log_2(log(4!..!)) – a.
This is therefore a question about the distribution of the numbers log_2(log(4!…!)) modulo 1. In particular, you can make 5 if log_2(log(4!…!)) ever lies between log_2(log(5))=0.6866 and log_2(log(6))=0.8414, all calculations done modulo 1.
In general, if you work out X = log_2(log(4!..!)) modulo 1, you can make :
1, always
2, if X < 0.13568 or X > 0.47123
3, if 0.13568 < X < 0.47123
4, if 0.47123 < X < 0.68656
5, if 0.68656 < X < 0.84138
6, if 0.84138 < X < 0.96044
7, if X < 0.05620 or X > 0.96044
8, if 0.05620 < X < 0.13568
and so on, as long as the number you are trying to make is not too big.
log_2(log(4!)) is 1.66814, which is equal to 0.66814 modulo 1. Therefore, it can make 1 or 2 or 4 (or 24).
log_2(log(4!!)) is 5.775702, which is equal to 0.775702 modulo 1. Therefore, it can make 1 or 2 or 5 (or 30 etc)
Using Stirling's series, I get log_2(log(4!!!))=84.78678213381762, so we can make 1 or 2 or 5 (or 31 etc)
It may be possible, using higher precision arithmetic than I have handy, to work out log_2(log(4!!!!)) modulo 1 to enough decimal places to see which integers can be formed. (I know it is possible to work out log_2(log(3!!!!)) mod 1 in this way)
It seems extremely unlikely to me that the values of log_2(log(4!..!)) modulo 1 could fail to be dense in [0,1]. In that case, every integer can be made, in an infinite number of different ways.
If the values of log_2(log(4!…!)) modulo 1 happen to be uniformly distributed in [0,1], then given b, the number n has a probability of log_2(log(n+1)/log(n)) of being formed. This is about 1/(nlog(2)) for larger n, so there's only a 34% chance, for any given number of factorials, of making 3. We've been unlucky so far.
In the above, log(x) = ln(x), log_2(x) = ln(x)/ln(2).
This sort of thing is why you should get MathJax support onto this website.
IMHO, the childish problem can get hard enough to at least qualify as an adolescent problem.
For the following problems, only the four basic arithmetic operations are legal (and parentheses, e.g., (a*b) + (c*d)). The object is to make 24 using all 4 four numbers. The hardest sets that I know of are:
3,3,7,7
4,4,7,7
1,5,5,5
2,7,8,9
3,3,8,8
Hmm…. unless I’ve made a mistake, 4!!!!, after about 10^27 square roots, gives …… 264, 16, 4, 2, 1, 1, 1, ……
@Tristan: Steve is being droll, alluding to a famous passage in Ecclesiastes.
@Ken B, @Tristan : 1 Corinthians 13:11 “When I was a child, I spoke as a child, I understood as a child, I thought as a child; but when I became a man, I put away childish things.”
@Mike H: Sure! Pick on a Sunday school drop-out!
:)
Sorry! :-)
Mike H:
***********************
let f(a,b) be the sqrt function applied a times to the
factorial function applied b times to 4.
Now, log(f(a,b)) is log(4!..!)/2^a
This is therefore a question about the distribution of
the numbers log_2(log(4!…!)) modulo 1. In particular,
you can make 5 if log_2(log(4!…!)) ever lies between
log_2(log(5))=0.6866 and log_2(log(6))=0.8414, all
calculations done modulo 1.
In general, if you work out X = log_2(log(4!..!)) modulo 1, you can make :
1, always
2, if X 0.47123
3, if 0.13568 < X < 0.47123
and so on,
It seems extremely unlikely to me that the values of
log_2(log(4!..!)) modulo 1 could fail to be dense in
[0,1]. In that case, every integer can be made, in an
infinite number of different ways.
********************************
This point is the crux of the question, the linchpin.
It has to be derived, not believed.
We're dealing with infinity, where intuition is
worthless. Talk of probability, likely, unlikely,
what's the chance, is all so many banana peels on
the sidewalk.
This is a deep problem, which would challenge the
best mathematicians. Proving it is hard, and if the
conjecture is false, that's even harder.
Another problem suggests itself: suppose the conjecture
is false. Then there are integers which cannot be
generated from the formula. So, devise a method which,
given any specified integer, will tell whether it is
generable via the formula. That would be the most
difficult challenge of all, possibly undecidable.
(and its undecidability might also be undecidable)