> I feel like the second you allow functions you've thrown the spirit of the game.
+, - (both binary and unary), ×, ÷ are functions, as is raising to a power. Why would you allow them?
As always in this kind of things, one can disagree about what constitutes an elementary function, but I don’t think taking square roots should be disqualified in this puzzle.
This is a good example of why you need rules on which functions are allowed. Repeated application of the successor function makes the entire exercise trivial
This is a great point. I think what you're really responding to is that it's a game without clear rules, and so part of the "game" is thinking about creative interpretations of the rules themselves and pushing the boundary of what others originally assumed the rules to be.
Granted there is creativity in this sort of game -- indeed, most "games" in life are like this -- but it's quite a different thing from winning a game with clearly defined rules like chess, or this game with the set of allowed operations specified up front.
I think a key distinction is that those are functions of two parameters. You can't just use them as many times as you like "for free" like the square root trick at the end of the article, because you need to "spend" at least one extra 2 on the second parameter each time.
That's not the whole story of course, you still need to agree on the set of allowed operations, but I think it makes a big difference even though it seems incidental at first.
> I wouldn’t call the construction given by Paul Dirac trivial. Do you think it is
Yes? It's doing exactly the thing that your parent comment complains about in the gamma function, introducing additional constants (in this case, mostly 2s) that, for no particular reason, don't count.
Why would you interpret squaring as consuming a 2, but square rooting as not consuming a 2?
That's exactly the point. What exactly, is the set of allowable functions used for the problem? I think you, and the post you reply to, are stating the same thing.
Where do you draw a line between "Functions available on a 4-function calculator" and "Functions I can make up specifically to generate a target integer"? I think you have to rigidly define this, or the game loses meaning.
This was my initial thought once we got to the Gamma function.
My reasoning is (I'm pretty sure it's the same as yours), why is the gamma function allowed, but not others? I could insert arbitrary functions to make the game arbitrarily solvable.
While this hit me at the Gamma introduction, I think it leads back to the beginning: It's a poorly defined problem from the rules at the start of the article. It should instead define the set of allowable functions (or operations) explicitly. I think you could modify this to retain the intent of showing how the problem scales with knowledge level.
It’s just about having fun at the end of the day, the gamma function and square root are considered fundamental enough. But if one wants they could try to limit to different subsets of functions and prove which numbers are possible or impossible to achieve just with those.
They also say “mathematical tools” not arbitrary functions.
I think you have a point, but as others have commented "allowing functions" is not the problem, as fundamental math operations are functions. But if we limit ourselves to only functions that map (tuples of) integers to integers ((Z, Z, ...) -> Z), the spirit of the original game is retained. This disallows sqrt and log, but retains addition, subtraction and multiplication (but not division). Factorial (n!) is allowed, as is exponentiation to a non-negative power.
Wonder if someone could come up with general solution within these constraints.
I think that, if you are restricted to a finite list of n-ary functions, n>=2, each returning a single value, then you can’t do it, as you will only have finitely many valid expressions.
This may be easier to see in a stack machine / RPN model. An expression is a list of operations, drawn from a finite set, each of is either “push the number 2” or something that decreases the stack size by at least 1. And you need exactly 4 pushes. So a valid expression has four pushes and at most 3 other operations, because otherwise the stack would underflow. This gives a finite number of possible expressions, but there are an infinite number of integers, so it can’t work.
I would argue that the Gamma function is more fundamental than the factorial operation. But you are still correct that if arbitrary functions were allowed, the game would degenerate to triviality.
Since in essence you can define your own functions f that give you any number you want from 2 (and for example not defined anywhere else). I.e. rules never said you can't use any function. They are vaguely saying "any mathematical operation".
I took a lot of math in my schooling, and have continued using math on a daily basis in my engineering career. I even subscribe to many math channels on YouTube, but this is the first time in my life that I've even heard of this function. I know there aren't real rules to this puzzle, but this function doesn't seem well-known at all.
There's nothing really in the definition of the successor function that necessarily requires that it's interpreted as n+1, though. It's just an interpretation from the context in which it's used. It could represent any operation as long as it is isomorphic to adding one -- but there's nothing special about "adding one". You could have it represent multiplying by a constant, and interpret "zero" as the number one.
So a number in this interpretation is either 1; or 2 times a natural number.
1, 2, 4, 8, 16, 32 -- you're working only with powers of 2 now.
The above "addition" rule above still works, but now it represents "multiplication" instead of addition. I'll replace all the S's in the above example with x2
So now, instead of addition, we've recursively defined multiplication where the successor function is interpreted as multiplying by 2. There's an infinite number of ways that you can interpret the successor function.
So basically, I do think it's cheating, and if you do want to define it as n+1, it would be even simpler to just define a function that takes any number to the desired output.
I'm not sure what kind of math schooling you did, but did you learn to construct the natural numbers from scratch?
This may have been the fault of math education. In my college people learn real analysis (constructing the real numbers) before they learn to construct the natural numbers, which is backwards to me. I recommend learning it: constructing the natural numbers from just sets in the tradition of Zermelo–Fraenkel is mind blowing the first time you see it. Of course you could just use Peano axioms without touching set theory too.
I had the same thought. Also with square roots hiding 2s behind notation, etc. The whole project isn’t really very coherent without specifying what specific operators you can use (and how many times).
See also: "Representing numbers using only one 4" written by a 26-year-old Donald Knuth in 1964 (https://www.jstor.org/stable/2689238 reprinted as Chapter 10 of his Selected Papers on Fun and Games) — it uses the single digit 4, and the three operations √x (square root), ⌊x⌋ (floor, i.e. greater integer not greater than), and x! (factorial), and ends with a (still unsolved) conjecture about whether every integer can be represented in this way.
The appendix (written for the book in 2011) points out an earlier (1962) 1.5-page paper π in Four 4's by J. H. Conway and M. J. T. Guy, written when they were students at Cambridge, that has a similar idea: https://archive.org/details/eureka-25/page/18/mode/1up?view=...
Maybe it's just me, but writing sqrt(2+2) instead of sqrt(2*2) or sqrt(2^2) was such an odd choice. It obfuscates the reason why 2=sqrt(2+2), and unnecessarily so.
Good point and feedback, but an odd choice by the author?
It could be the phenomenon of the author's cognitive bandwidth being consumed by everything in the article, including each argument, the overall argument, the writing, the formatting, etc. etc., and with time pressures. The critic can focus at their leisure on one point, with bandwidth to spare - and so it's obvious! :)
Because sqrt is the reverse of 2^2 and 2*2 (which is 2^2 unwrapped). Though there's no direct relationship between sqrt and 2+2 other than that it happens to be equal to 2*2.
Or put differently: N = sqrt(N^2) or sqrt(N * N) for every positive N, but x = sqrt(x + x) or sqrt(x + 2) is only true for x = 2 for both or x = 0 for the first representation.
I think my preference is more towards conciseness.
I made a stack machine with single character instructions and needed to solve a variation of this problem. I had just the digits 0 through 9. The characters '23' would be push 2 followed by push 3. To actually represent the number 23 you would use
45*3+
or something similar.
That left me with the problem of how to encode each integer in the fewest characters.
Tools at hand.
The digits 0 through 9
'P': Pi
'*': (a * b),
'/': (a / b),
'-': (a - b),
'+': (a + b),
's': sin(a),
'c': cos(a),
'q': sqrt(a),
'l': log(a),
'~': abs(a),
'#': round(a),
'$': Math.floor(a),
'C': clamp(a),
'<': min(a, b),
'>': max(a, b),
'^': pow(a, b),
'a': atan2(a, b),
'%': positiveMod(a, b),
'!': (1 - a),
'?': (a <= 0 ? 0 : 1)
'o': a xor b scaled by c; ((a*c) xor (b*c))/c
'd': duplicate the top stack entry
':': swap the top two stack entries
';': swap the top and third stack entries
I have wondered about revisiting the stack machine with a complex number stack to see what I can come up with.
(Next time I post something like this I am not going to use my phone)
Kolmogorov complexity is uncomputable because it admits Turing complete languages, and reduces to the halting problem. If the language you admit isn't Turing complete, then the Kolmogorov complexity of the thing is computable.
It looks like OP's language is not Turing complete. It always terminates. You can just do a breadth first search on the program space. The first program you get that outputs the number you want is the shortest program.
If it were Turing complete, you can't do this, because eventually you'll find a program that just keeps running for like a really long time. Is it running because the program never halts? Or is will it halt eventually and output the number you want? You can't know for sure.
What about making each digit be the instruction "times 10 plus digit", with a different instruction to push a 0, like a space? Then you can represent 23 with " 23".
Root notation isn't really _concealing_ anything. The fact that it's mostly equivalent to exponentiation by half is a theorem. Do we need to admit that 2 is concealing 1+1, thus making the game impossible?
Given the prevalence of quadratic polynomials over higher-order ones, sqrt does feel somewhat more fundamental than arbitrary exponentiation.
Lots of people have pointed out the farcity of the game after allowing fancy functions, but IMHO, there is a lot of fun in just finding satisfying solutions, without the need for specific rule limitations.
The root notation is a syntax with a place for a number, to specify the degree. For instance ∛ -> cube root(s). When the degree is 2, it can be omitted.
So yes, the notation conceals something: its default value.
Related: there as a reverse engineering/CTF challenge (which shall remain nameless to prevent you from cheating) where my solution involved injecting shellcode that adds specific number to the stack pointer. But your shellcode -- including the number(s) you add -- can only involve bytes from the ascii alphanumeric set.
So I used a SAT solver to find a combination of numbers, not using prohibited bytes, that add up to the number I really want.
This reminds me of this mobile game Tchisla[0] where you have to build all numbers up to 1000 (10000?) using only a given digit and a couple of operators (including sqrt and !)
It was a lot of fun, you tend to develop strategies and the game has a simple, efficient UX. Fair warning, it is very time consuming.
Readit News
Ex, the gamma function is (n-1)! So now you're making 7 with four twos and a one. You've broken the spirit.
If I can hide numbers in a function call... It's trivially easy to always succeed.
+, - (both binary and unary), ×, ÷ are functions, as is raising to a power. Why would you allow them?
As always in this kind of things, one can disagree about what constitutes an elementary function, but I don’t think taking square roots should be disqualified in this puzzle.
> Ex, the gamma function is (n-1)!
And 2 is just S(S(0)) (https://en.wikipedia.org/wiki/Peano_axioms)
> If I can hide numbers in a function call... It's trivially easy to always succeed.
I wouldn’t call the construction given by Paul Dirac trivial. Do you think it is, or do you know of a simpler one?
This is a good example of why you need rules on which functions are allowed. Repeated application of the successor function makes the entire exercise trivial
Granted there is creativity in this sort of game -- indeed, most "games" in life are like this -- but it's quite a different thing from winning a game with clearly defined rules like chess, or this game with the set of allowed operations specified up front.
That's not the whole story of course, you still need to agree on the set of allowed operations, but I think it makes a big difference even though it seems incidental at first.
Yes? It's doing exactly the thing that your parent comment complains about in the gamma function, introducing additional constants (in this case, mostly 2s) that, for no particular reason, don't count.
Why would you interpret squaring as consuming a 2, but square rooting as not consuming a 2?
Where do you draw a line between "Functions available on a 4-function calculator" and "Functions I can make up specifically to generate a target integer"? I think you have to rigidly define this, or the game loses meaning.
Deleted Comment
My reasoning is (I'm pretty sure it's the same as yours), why is the gamma function allowed, but not others? I could insert arbitrary functions to make the game arbitrarily solvable.
While this hit me at the Gamma introduction, I think it leads back to the beginning: It's a poorly defined problem from the rules at the start of the article. It should instead define the set of allowable functions (or operations) explicitly. I think you could modify this to retain the intent of showing how the problem scales with knowledge level.
They also say “mathematical tools” not arbitrary functions.
Wonder if someone could come up with general solution within these constraints.
This may be easier to see in a stack machine / RPN model. An expression is a list of operations, drawn from a finite set, each of is either “push the number 2” or something that decreases the stack size by at least 1. And you need exactly 4 pushes. So a valid expression has four pushes and at most 3 other operations, because otherwise the stack would underflow. This gives a finite number of possible expressions, but there are an infinite number of integers, so it can’t work.
2 + 2 + 2 + floor(sqrt(2))
Which feels at least more in the spirit of the challenge than gamma.
BUT I did not use "44", which I did see in some solutions. That seemed out of bounds to me!
It's a little "brain teaser" game, to encourage kids to practice fairly basic math. Don't take it too far out of context.
Maybe. But I doubt many people are aware of such functions, so it's still a fun challenge.
Yeah this feels like those "Implemented XYZ in 1 line"
Okay, then this is easy, just use the successor function.
Etc.https://en.wikipedia.org/wiki/Peano_axioms
It's probably something that only folks who study the foundations of mathematics would know.
You may have also heard about it if you learned about Gödel's incompleteness theorems, or read Gödel, Escher, Bach
A natural number is either zero or a successor of a natural number.
Addition is defined as a recursive application of successor functions.
as an example -- 3 + 2:S(S(S(0))) + S(S(0)) = S( S(S(S(0))) + S(0) ) = S( S( S(S(S(0))) + 0 ) ) = S(S(S(S(S(0)))))
There's nothing really in the definition of the successor function that necessarily requires that it's interpreted as n+1, though. It's just an interpretation from the context in which it's used. It could represent any operation as long as it is isomorphic to adding one -- but there's nothing special about "adding one". You could have it represent multiplying by a constant, and interpret "zero" as the number one.
So a number in this interpretation is either 1; or 2 times a natural number.
1, 2, 4, 8, 16, 32 -- you're working only with powers of 2 now.
The above "addition" rule above still works, but now it represents "multiplication" instead of addition. I'll replace all the S's in the above example with x2
2x2x2x1 "+" 2x2x1 = 2x(2x2x2x1 + 2x1) = 2x(2x(2x2x2x1 + 1) = 2x2x2x2x2x1 = 32
So now, instead of addition, we've recursively defined multiplication where the successor function is interpreted as multiplying by 2. There's an infinite number of ways that you can interpret the successor function.
So basically, I do think it's cheating, and if you do want to define it as n+1, it would be even simpler to just define a function that takes any number to the desired output.
This may have been the fault of math education. In my college people learn real analysis (constructing the real numbers) before they learn to construct the natural numbers, which is backwards to me. I recommend learning it: constructing the natural numbers from just sets in the tradition of Zermelo–Fraenkel is mind blowing the first time you see it. Of course you could just use Peano axioms without touching set theory too.
The appendix (written for the book in 2011) points out an earlier (1962) 1.5-page paper π in Four 4's by J. H. Conway and M. J. T. Guy, written when they were students at Cambridge, that has a similar idea: https://archive.org/details/eureka-25/page/18/mode/1up?view=...
For example,
because 24! lies between 5^{32} and 6^{32}.It could be the phenomenon of the author's cognitive bandwidth being consumed by everything in the article, including each argument, the overall argument, the writing, the formatting, etc. etc., and with time pressures. The critic can focus at their leisure on one point, with bandwidth to spare - and so it's obvious! :)
I wasn't criticizing him for this, but rather fascinated that this is the variant that was chosen.
12 = 2 * (2+2+2)
Is a hell or a lot simpler than using complex numbers. Might be a different example for that would have been better.
Or put differently: N = sqrt(N^2) or sqrt(N * N) for every positive N, but x = sqrt(x + x) or sqrt(x + 2) is only true for x = 2 for both or x = 0 for the first representation.
I made a stack machine with single character instructions and needed to solve a variation of this problem. I had just the digits 0 through 9. The characters '23' would be push 2 followed by push 3. To actually represent the number 23 you would use
That left me with the problem of how to encode each integer in the fewest characters.Tools at hand.
I have wondered about revisiting the stack machine with a complex number stack to see what I can come up with.(Next time I post something like this I am not going to use my phone)
https://en.wikipedia.org/wiki/Kolmogorov_complexity
It looks like OP's language is not Turing complete. It always terminates. You can just do a breadth first search on the program space. The first program you get that outputs the number you want is the shortest program.
If it were Turing complete, you can't do this, because eventually you'll find a program that just keeps running for like a really long time. Is it running because the program never halts? Or is will it halt eventually and output the number you want? You can't know for sure.
https://c50.fingswotidun.com/
Which gives you a finite problem. The VM cannot loop or define functions (yet, anyway) so it doesn't go all busy beaver on you.
One small wrinkle, if you ignore the fact that the root notation conceals exponentiation by 1/2, by making that common value a default.
That's a lot of hidden 2's!
Given the prevalence of quadratic polynomials over higher-order ones, sqrt does feel somewhat more fundamental than arbitrary exponentiation.
Lots of people have pointed out the farcity of the game after allowing fancy functions, but IMHO, there is a lot of fun in just finding satisfying solutions, without the need for specific rule limitations.
So yes, the notation conceals something: its default value.
So I used a SAT solver to find a combination of numbers, not using prohibited bytes, that add up to the number I really want.
https://docs.google.com/presentation/d/19K7SK1L49reoFgjEPKCF...
It was a lot of fun, you tend to develop strategies and the game has a simple, efficient UX. Fair warning, it is very time consuming.
[0] https://apps.apple.com/fr/app/tchisla-number-puzzle/id110062...