Making any integer with four 2s(eli.thegreenplace.net)
eli.thegreenplace.net
Making any integer with four 2s
https://eli.thegreenplace.net/2025/making-any-integer-with-four-2s/
177 comments
> 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.
> 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?
+, - (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?
> And 2 is just S(S(0))
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 good example of why you need rules on which functions are allowed. Repeated application of the successor function makes the entire exercise trivial
But also, if the criteria for allowed functions is that they are "reasonable, elemental" (as per the fine article), then I think it would be quite hard to come up with a set of rules to encode that in a way that includes log() and sqrt(), but not S(). It's hard to imagine a function that is less elemental than S() (except maybe the identity function), or why its inclusion would be unreasonable when the other two aren't.
Given how the article is laid out, I think it would be more appropriate to view the game from the lens of when we teach the operations in school, as opposed to what are fundamental or elementary operations / functions in math.
Though I also think square root is cheating, it has an implicit 2 inside of it, where as raising to the power of 2 and log 2 are explicit.
You could also argue for only infix operators.
A good game must be somewhat challenging or else it is not really a game. Anything that makes the game trivial ought be omitted for it to be a game.
Though I also think square root is cheating, it has an implicit 2 inside of it, where as raising to the power of 2 and log 2 are explicit.
You could also argue for only infix operators.
A good game must be somewhat challenging or else it is not really a game. Anything that makes the game trivial ought be omitted for it to be a game.
Yeah, thinking of the puzzle as a game, rather than a competition, allows for a different perspective.
If I think of a competition, then I'd expect the rules to be determined ahead of time according to some pre-imagined criteria. If someone manages to find a clever hack within the rules that allows for trivial "breaks", then that's good for them and they just get to beat everyone else at it.
But if I think of a game, then it's much more natural for the rules to adapt over time as people realise that some types of "play" make the game less fun, or straight-up boring. They don't have to be self-consistent, or logical. They're essentially arbitrary, and just whatever they need to be to make the game "better".
If I think of a competition, then I'd expect the rules to be determined ahead of time according to some pre-imagined criteria. If someone manages to find a clever hack within the rules that allows for trivial "breaks", then that's good for them and they just get to beat everyone else at it.
But if I think of a game, then it's much more natural for the rules to adapt over time as people realise that some types of "play" make the game less fun, or straight-up boring. They don't have to be self-consistent, or logical. They're essentially arbitrary, and just whatever they need to be to make the game "better".
My criteria are "no letters or digits from any language" (other than 2). So you can't use the log or S() or the gamma function, but you can use sqrt, because there is accepted symbology that does not require any atom of non-mathematical language to represent.
What if it turns out that the radical (square root) symbol is a letter from a language (if a little squished)? And we somehow figure out one day which letter it is, for sure?
https://en.wikipedia.org/wiki/Radical_symbol#Origin
https://en.wikipedia.org/wiki/Radical_symbol#Origin
APL programmers enter the room
While you are right that Succ() is as elemental as it gets (including in both Peano and set-theory construction of natural numbers), it is seldom used outside of theoretical foundations.
So perhaps the implied rule is not about it being "reasonable, elemental", but rather about "common" functions and operands (yes, it's still a can of worms, and you'd need to be explicit about what that is).
So perhaps the implied rule is not about it being "reasonable, elemental", but rather about "common" functions and operands (yes, it's still a can of worms, and you'd need to be explicit about what that is).
> While you are right that Succ() is as elemental as it gets (including in both Peano and set-theory construction of natural numbers), it is seldom used outside of theoretical foundations.
Well, depends on how you define seldom. What if I told you that twitter would break without the use of Succ()? :-)
Well, depends on how you define seldom. What if I told you that twitter would break without the use of Succ()? :-)
As I said in the other paragraph:
> it's still a can of worms
;-)
> it's still a can of worms
;-)
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.
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.
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.
Surely we accept unary minus as one of our functions? Once we accept one unary function we're just quibbling over details.
I agree that you need to define and agree upon a finite set of allowed operations before playing the game. IMHO, square root, logarithm/exp, floor/round/ceiling, sin/cos/tan ought to be included in the list. But that's just like, my opinion, man.
I agree that you need to define and agree upon a finite set of allowed operations before playing the game. IMHO, square root, logarithm/exp, floor/round/ceiling, sin/cos/tan ought to be included in the list. But that's just like, my opinion, man.
But repeated application of the unary minus basically results in a no-op. So it’s somewhat exceptional in that regard.
> 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?
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?
Because of our standard notation for those
You are inferring that as a rule of the game by making assumptions. There are other conclusions different people could reach.
And those other people are free to do whatever they like in their interpretation of the game.
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.
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.
Right, I invented the jrockway function which is defined as f(2, 2, 2, 2) = 7 so I made 7. Maybe the rule is "someone else has to invent the function", but I invented that so you can use it. (Please make me a the__alchemist function.)
Maybe the rule should be that the function has to be invented before the inventor has knowledge of this game. But now I'm just going through /usr/bin looking for binaries where the 2222th byte is 0x7.
Maybe the rule should be that the function has to be invented before the inventor has knowledge of this game. But now I'm just going through /usr/bin looking for binaries where the 2222th byte is 0x7.
Let karparov(2222) be defined as the number of whole seconds that have elapsed since this message was posted. You cover all naturals this way!
But you're all missing the point. A winning "solution" to this game is whatever the reader accepts as a legal solution which at the same time is as creative as possible. That's necessarily subjective, but that's fine. Anybody is free to argue that it's a stupid game if these are the rules, and those folks just don't need to play and can let everybody else have some fun!
But you're all missing the point. A winning "solution" to this game is whatever the reader accepts as a legal solution which at the same time is as creative as possible. That's necessarily subjective, but that's fine. Anybody is free to argue that it's a stupid game if these are the rules, and those folks just don't need to play and can let everybody else have some fun!
Perfect! Over time I will eventually win this game!
[deleted]
It sounds like you've just found one for >=2: 2, S(2), S(S(2)), ...
That, somewhat ironically, typically isn’t included in the set of elementary functions. ‘plus’ is, but ‘plus one’ isn’t.
That gets at what makes using additional functions like in the blog post a bit arbitrary: we don't have special notation for "+ 1" or "* 2", but we do for "^(1/2)" and "log_2". It's not hard to imagine a different world where "+ 1" or "^2" had special notation, and suddenly we'd be able to solve the question in even simpler ways.
It's still a fun puzzle, it's just based more on our shared notational conventions as much as the underlying math.
It's still a fun puzzle, it's just based more on our shared notational conventions as much as the underlying math.
Maybe they meant symbolic operators feel alright but named functions feel like cheating, so 2+2+2+⌊√2⌋ is fine but 2+2+2+floor(sqrt(2)) is not.
[deleted]
you shouldn't be able to use letters. You're supposed to use four 2s and symbols, not four 2s plus the letters "l", "o", "g".
But letters are symbols too.
(Mostly goes to show that it's really hard to be precise and allow some mathematical language and disallow some)
(Mostly goes to show that it's really hard to be precise and allow some mathematical language and disallow some)
I would say that any function that implicitly favors a single number must be explicitly stated, and thus, if used for this game, be the number 2. So all uses of the radical must state which root (2). Dirac's solution then wouldn't work because the use of 2 is O(n).
Logs would also need to state the base. No implicit use of e or 10, and lg wouldn't be allowed in place of log2.
I haven't said much other than logs and roots are binary operators with one of the operands usually implicit in the notation, so if we don't have special notation for powers and exponentiation, then we shouldn't allow the same for their inverse operations.
Logs would also need to state the base. No implicit use of e or 10, and lg wouldn't be allowed in place of log2.
I haven't said much other than logs and roots are binary operators with one of the operands usually implicit in the notation, so if we don't have special notation for powers and exponentiation, then we shouldn't allow the same for their inverse operations.
Why not?
Why is it ok to use "22" = 2 * 10^1 + 2 (when it could be a number in base 3 — 2 * 3^1 + 2 = 8 decimal — or any other base)? This implies base 10, just like root implies base 2, or ln means e.
As I said, this is a game, and trying to imply certain artificial constraints will be really hard with how abstract maths is.
Again, mention of successor function is apt: everything else is built from 1, succ() and another axiom, definition or so. So everything else can be reduced to this.
Why is it ok to use "22" = 2 * 10^1 + 2 (when it could be a number in base 3 — 2 * 3^1 + 2 = 8 decimal — or any other base)? This implies base 10, just like root implies base 2, or ln means e.
As I said, this is a game, and trying to imply certain artificial constraints will be really hard with how abstract maths is.
Again, mention of successor function is apt: everything else is built from 1, succ() and another axiom, definition or so. So everything else can be reduced to this.
I said that this implicit use of 10 or some other number shouldn't be allowed. So log, ln, lg (i.e base 2) shouldn't be allowed, but log_b(x) where b and x are states is OK, just as 10^x, e^x, and 2^x require you to explicitly expose the base (and for this puzzle, disallow 10 and e since neither is a 2).
Successor is essentially s(n) = n + 1, so that shouldn't be allowed either.
Successor is essentially s(n) = n + 1, so that shouldn't be allowed either.
FWIW, "successor" is not really n + 1: you've got that the other way around.
Successor simply "is" (it's a relation that satisfies a number of conditions), and summation is defined in terms of successor function.
My point is that you can really define everything in terms of these primitive definitions, which means that there won't be any single use of a non-2 digit for any function, or you'll be going with a set of arbitrary allowances.
But the whole point should be: what are those arbitrary constraints that make the game fun? And once you clear that bar, it's ok to open up the next one (this does not make them non-arbitrary though).
Basically, I am saying your take at those arbitrary decisions is not a very fun one ;-)
Successor simply "is" (it's a relation that satisfies a number of conditions), and summation is defined in terms of successor function.
My point is that you can really define everything in terms of these primitive definitions, which means that there won't be any single use of a non-2 digit for any function, or you'll be going with a set of arbitrary allowances.
But the whole point should be: what are those arbitrary constraints that make the game fun? And once you clear that bar, it's ok to open up the next one (this does not make them non-arbitrary though).
Basically, I am saying your take at those arbitrary decisions is not a very fun one ;-)
Yeah no they're not. If I give you the list "abc/=^" absolutely everybody agrees which ones are symbols and which ones are letters. What you meant to say is that it's really easy to be precise, if you are operating on human language instead of mathematical pedantry.
How about adding αβγδ or ℵ (aleph) to that list? Or шћдж? Or add Chinese or Arabic letters to the list.
Letters are symbols used to write down words of a natural language.
If you are unfamiliar with a language, you are more likely to call them "symbols" instead of "letters".
Letters are symbols used to write down words of a natural language.
If you are unfamiliar with a language, you are more likely to call them "symbols" instead of "letters".
Those are clearly all letters in the sense of the spirit of the game. It's pretty unambiguous.
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.
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.
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.
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.
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.
Are you sure the number of possible expressions is finite? Or is it countably infinite? I could in theory make an arbitrarily long expression out of the four fundamental operators, and because I can derive -1 from a finite set of operations it is possible to derive any integer from any even integer. You can also derive zero from the rules.
> I could in theory make an arbitrarily long expression out of the four fundamental operators
Not with only four inputs you can't. You can only have three operations, because you have no way of getting another input parameter.
Not with only four inputs you can't. You can only have three operations, because you have no way of getting another input parameter.
I didn't mean to say that n would need to be 2 or more, unary functions (I even mentioned factorial) should be fine. 1-tuple is valid tuple :)
And yes I think your analysis that only allowing n-ary funcs with n>=2 would make general solution very much impossible since you can only have a limited number of inputs.
And yes I think your analysis that only allowing n-ary funcs with n>=2 would make general solution very much impossible since you can only have a limited number of inputs.
f_n(a,b,c,d) = n is a mapping from Z^4 to Z
The Dirac solution doesn’t involve gamma, just N square roots and 2 logarithms.
But the square root has a hidden operand, 2. We don't write it because by convention the default root is 2, but that still feel like cheating to me.
This is why people have brought up the successor function too: A + B, is, by definition
B applications of Succ() on A:
The mathematical root probably first appeared as a square root and was later extended to support other exponents.
But is there any fun in this? As noted elsewhere, the game is in finding the rules, and a solution within those rules.
[]Since all the natural numbers other than 1 are defined using a Succ() functions, there's a trivial solution. But if we only limit ourselves to this most elementary operation, we can't get a 1 because that's an axiom in itself ("There exists 1" or "There is a set of cardinality 1").
A + B = Succ(Succ(Succ(...Succ(A))))
The mathematical root probably first appeared as a square root and was later extended to support other exponents.
But is there any fun in this? As noted elsewhere, the game is in finding the rules, and a solution within those rules.
[]Since all the natural numbers other than 1 are defined using a Succ() functions, there's a trivial solution. But if we only limit ourselves to this most elementary operation, we can't get a 1 because that's an axiom in itself ("There exists 1" or "There is a set of cardinality 1").
I think the correct definition of A + B is
A + 0 = A (or A + 1 = Succ(A), if you insist 0∉ℕ)
A + Succ(B) = Succ(A) + BNot sure what you mean with "correct", because "correct" is an equivalence class of slightly different definitions? Eg. https://en.wikipedia.org/wiki/Peano_axioms has, instead of both yours and mine:
A + 0 = A
A + Succ(B) = Succ(A + B)
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.
Inorite. If we're allowing any old function, then I can just define 12345 as
Onetwothreefourfive()-2+2-2+2You don't even need gamma for 7:
2 + 2 + 2 + floor(sqrt(2))
Which feels at least more in the spirit of the challenge than gamma.
2 + 2 + 2 + floor(sqrt(2))
Which feels at least more in the spirit of the challenge than gamma.
The article already has a solution for 7 (and any other number) that doesn't use the gamma function.
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".
There's a version of this with "4"s that I have done through 20. I have used factorials and square roots but nothing more. I felt dirty.
BUT I did not use "44", which I did see in some solutions. That seemed out of bounds to me!
BUT I did not use "44", which I did see in some solutions. That seemed out of bounds to me!
> I feel like...you've thrown the spirit of the game.
It's a little "brain teaser" game, to encourage kids to practice fairly basic math. Don't take it too far out of context.
It's a little "brain teaser" game, to encourage kids to practice fairly basic math. Don't take it too far out of context.
That's just what it evaluates to on integers. The standard definition of it also includes e and an integral from 0 to ∞.
> You've broken the spirit.
Maybe. But I doubt many people are aware of such functions, so it's still a fun challenge.
Maybe. But I doubt many people are aware of such functions, so it's still a fun challenge.
> If I can hide numbers in a function call
Yeah this feels like those "Implemented XYZ in 1 line"
Yeah this feels like those "Implemented XYZ in 1 line"
import XYZ7 = Math.ceil(Math.random(2))+2*2+2
> use any mathematical operations
Okay, then this is easy, just use the successor function.
Okay, then this is easy, just use the successor function.
S(n) = n+1
6 = 2*2*2-2
7 = S(2*2*2-2)
8 = S(S(2*2*2-2))
I feel like having a 1 on the first line is cheating given the constraint "using no other digits".
By that argment you shouldn't be able to use factorial function either, because that has a "hidden 1" too:
fac(n) = n * fac(n-1) n>0
= 1 n=0The one here isn't hidden in any way – it's on the very first line. You might as well just define X = 7 and do 2-2+2-2+X.
I'm not "defining" anything; I'm just using fairly bog standard math that has been around for hundreds of years.
S(N) is just S(N), it's not N+1 unless you define it that way. S(0) is not 1, it's S(0). The successor function doesn't really get mapped to numbers without an explicit additional mapping.
Unless you are talking about an alternative number system where 1+1 is not 2 then yes, S(0) is 1.
No, it's not. That's just the standard model of peano arithmetic. You can map the successor function to many different operations and objects that aren't even numbers.
Yes it is. "1" is just a label for what is also known as S(0) no mater what other ways you invent to refer to that element. Just like 一 is another label for the same concept.
log is also using another digit.
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.
It has a rich history going back to the formalization of arithmetic in the 1800s.
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
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
The successor function is how natural numbers are defined in most axiomatic arithmetic systems.
A natural number is either zero or a successor of a natural number.
Addition is defined as a recursive application of successor functions.
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.
A natural number is either zero or a successor of a natural number.
Addition is defined as a recursive application of successor functions.
m + 0 = m,
m + S(n) = S(m + n).
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.
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.
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.
Finding the shortest expression with 4 2's for a given integer would be a more interesting challenge
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=...
For example,
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,
5 = ⌊√√√√√(4!)!⌋
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! :)
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 agree it potentially wasn't a conscious choice, but it's still interesting nonetheless.
I wasn't criticizing him for this, but rather fascinated that this is the variant that was chosen.
I wasn't criticizing him for this, but rather fascinated that this is the variant that was chosen.
Speaking of odd choices:
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.
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.
Sorry, the intention was just to show a cool use of complex numbers, not claim this is the simplest method to generate 12 which is pretty simple, as you demonstrate.
Maybe there's a "golf score" somewhere that rewards less expensive operations. The "Dirac hack" would run up a lot of points.
Really? But why? All of 2+2, 2*2 2^2 are trivially 4, and sqrt(4)=2 so why is the + more odd than others?
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.
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.
If 2*2 is 2^2 unwrapped, then surely 2+2 is 2*2 unwrapped, thus 2+2 is 2^2 unwrapped^2 and is also natural via transitivity? :P
Though as I said in the rest of my comment, the 2+2 unwrap only works for N=2. So it's not a general unwrap, but rather a specific example that happens to work for N=2.
The 2*2 also doesn't seem a general unwrap.
2^2 -> 2*2 -> 2+2
2^3 -> 2*2*2 -> (2+2)+(2+2)
2^2 -> 2*2 -> 2+2
2^3 -> 2*2*2 -> (2+2)+(2+2)
It's not N^Y, it's N^2 as we are talking about the reverse of sqrt which is N^(1/2).
N^2 == N*N != N+N
N^2 == N*N != N+N
N^2 = N*N = Sum_i=1 to N of N.
More generally "unwrap" is being used as inlining the recursive hyper operation once more: https://en.wikipedia.org/wiki/Hyperoperation
More generally "unwrap" is being used as inlining the recursive hyper operation once more: https://en.wikipedia.org/wiki/Hyperoperation
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
Tools at hand.
(Next time I post something like this I am not going to use my phone)
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.
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
(Next time I post something like this I am not going to use my phone)
The answer in general may be uncomputable.
https://en.wikipedia.org/wiki/Kolmogorov_complexity
https://en.wikipedia.org/wiki/Kolmogorov_complexity
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.
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.
[deleted]
AHH but in practice you are limited to 50 characters.
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.
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.
I thought it would be possible to use the (undocumented?) T instruction and use the time variable as persistent memory, but it seems to reset each step. It would be nice if there were a way to store things across time steps!
ooh, hadn't thought about persistence. I always considered all executions running in isolation (and not necessarily in-order). Persistence would have to decide if it was localized to the same pixel, next frame or pass between pixels. A possibility for that is an instruction that sets a value in a buffer at the same resolution of the output and a paired instruction that reads the buffer generated the previous frame (with location popped from stack) so if { was write to buffer, it writes the top stack value to the buffer at the same location as the pixel output. using } to read would mean if you started a program with "xy}" would place the value from the buffer on the stack. It would also allow fade and blur effects.
In a similar vein I had wondered about a kernel function that read from a buffer with a 3x3 kernel on the stack.
Perhaps I should revisit the idea. Using a stack with multiple lanes of floats would potentially richer operations, colors, complex numbers, quaternions? 4 lanes could potentially Even storing the top value of the stack at the base for the next frame. Or, (new idea) a cyclic buffer stack of a fixed length. That wouldn't require any memory management at render time, and could persist multiple values just by popping them off.
I'm not sure how that would impact the speed. At the moment the stack expressions are converted into JavaScript expressions for the JIT to make fast. I'd have to go back to requiring an actual stack again.
In a similar vein I had wondered about a kernel function that read from a buffer with a 3x3 kernel on the stack.
Perhaps I should revisit the idea. Using a stack with multiple lanes of floats would potentially richer operations, colors, complex numbers, quaternions? 4 lanes could potentially Even storing the top value of the stack at the base for the next frame. Or, (new idea) a cyclic buffer stack of a fixed length. That wouldn't require any memory management at render time, and could persist multiple values just by popping them off.
I'm not sure how that would impact the speed. At the moment the stack expressions are converted into JavaScript expressions for the JIT to make fast. I'd have to go back to requiring an actual stack again.
Reminds me of https://www.hacker.org/hvm/ (2008)
I suspect a whole lot of numbers are going to get encoded in base 9 or 10 as mostly repetitions of digit + * digit + * or equivalent.
> There's just one small wrinkle: it uses three instances of the digit 2, not four.
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!
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!
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.
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.
So yes, the notation conceals something: its default value.
I have a function f: R -> R such that f(0)=1 and f'(x)=f(x). Is this concealing a parameter? It turns out we can deduce that f(x)=e^x, so f(x)=pow(e,x), so maybe? But wait, is pow concealing another parameter? Indeed, exponentiation is just (a completion over) repeated multiplication; multiplication is repeated addition, and addition repeated succesorship. It's straightforward to show that pow(x,y)=f(2,x,y) where f(n,x,y) encodes said hierarchy. But wait! f is a function, which is a set of 2-tuples, so we have another "hidden" parameter. It's also essentially part of Fast growing hierarchy[0] functions. Or what if we extend to complex numbers? Is the imaginary axis degree of freedom another hidden parameter?
Et cetera ad infinitum...
So, if you want to say that sqrt(x) has a hidden parameter, you're just making an arbitrary claim unless you accept it is concealing an unbounded number of hidden parameters.
Or we can just do the obvious thing and say that sqrt(x) has one parameter.
[0]:https://googology.fandom.com/wiki/Fast-growing_hierarchy
Et cetera ad infinitum...
So, if you want to say that sqrt(x) has a hidden parameter, you're just making an arbitrary claim unless you accept it is concealing an unbounded number of hidden parameters.
Or we can just do the obvious thing and say that sqrt(x) has one parameter.
[0]:https://googology.fandom.com/wiki/Fast-growing_hierarchy
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.
https://docs.google.com/presentation/d/19K7SK1L49reoFgjEPKCF...
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...
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.
[0] https://apps.apple.com/fr/app/tchisla-number-puzzle/id110062...
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...
There's the classic “four fours”, which I learned as a child in the book “The Man Who Counted”.
https://en.wikipedia.org/wiki/Four_fours
https://en.wikipedia.org/wiki/The_Man_Who_Counted
https://en.wikipedia.org/wiki/Four_fours
https://en.wikipedia.org/wiki/The_Man_Who_Counted
That's version I learned as a kid. You might enjoy this page of mine:
The Definitive Four Fours Answer Key https://dwheeler.com/fourfours/
The Definitive Four Fours Answer Key https://dwheeler.com/fourfours/
I love this:
> Note that these are large files; both are over 1.6 Megabytes, so don’t load these if you have a slow Internet connection
Just shows how far internet speeds have come...
> Note that these are large files; both are over 1.6 Megabytes, so don’t load these if you have a slow Internet connection
Just shows how far internet speeds have come...
That's the one!
That's how I learned about false induction. I also liked the one about the men who were lined up and had something on their backs and they had to guess what it was.
That's how I learned about false induction. I also liked the one about the men who were lined up and had something on their backs and they had to guess what it was.
[deleted]
This is amazing, but there are a lot of 2's hiding in those sqrt symbols
Here are some values that are (understandably) not listed on the blog. They happen only due to the limited precision of floating point formats.
My old solvers from what feels like a previous life: https://madflame991.blogspot.com/2013/02/four-fours.html https://madflame991.blogspot.com/2013/02/return-of-four-four...
That was fun
128 = √(2 / √√(√2 - (2 / √2)))
8192 = √√(2 / ((√2 * √2) - 2))
16384 = (2 / √√(√2 - (2 / √2)))
67108864 = √(2 / ((√2 * √2) - 2))
134217728 = (2 / √(√2 - (2 / √2)))
4503599627370496 = (2 / ((√2 * √2) - 2))
9007199254740992 = (2 / (√2 - (2 / √2)))
6369051672525773 = (√2 / (√2 - (2 / √2)))
My old solvers from what feels like a previous life: https://madflame991.blogspot.com/2013/02/four-fours.html https://madflame991.blogspot.com/2013/02/return-of-four-four...
That was fun
When everything is an IEEE 754 floating point number, a mathematically "linear" function can indeed be coerced into anything: http://tom7.org/grad/
Nice! Looking into them a bit deeper, they all rely on two facts involving quantities that are off by 1 ulp:
√2 - 2/√2 as a float64 is exactly equal to 2^{-52}
√2 * √2 as a float64 is exactly equal to 2 + 2^{-51}
√(2 / √√(√2 - (2 / √2))) := √(2 / √√(2^{-52})) = √(2 / 2^{-13}) = 2^7 = 128
√√(2 / ((√2 * √2) - 2)) := √√(2 / 2^{-51}) = √√(2^{52}) = 2^{13} = 8192
6369051672525773 = 2^{52} * 1.4142135623730951454746218587388284504413604736328125
Very clever, but using an arbitrary number of square roots seems almost cheating since it’s practically another symbol for a “2” (exponent of 1/2)
I would allow it, given they physically write down all N square root on a piece of paper.
> I've read about this story in Graham Farmelo's book The Strangest Man: The Hidden Life of Paul Dirac, Quantum Genius.
"The Strangest Man": https://en.wikipedia.org/wiki/The_Strangest_Man
Four Fours: https://en.wikipedia.org/wiki/Four_fours :
> Four fours is a mathematical puzzle, the goal of which is to find the simplest mathematical expression for every whole number from 0 to some maximum, using only common mathematical symbols and the digit four. No other digit is allowed. Most versions of the puzzle require that each expression have exactly four fours, but some variations require that each expression have some minimum number of fours.
"The Strangest Man": https://en.wikipedia.org/wiki/The_Strangest_Man
Four Fours: https://en.wikipedia.org/wiki/Four_fours :
> Four fours is a mathematical puzzle, the goal of which is to find the simplest mathematical expression for every whole number from 0 to some maximum, using only common mathematical symbols and the digit four. No other digit is allowed. Most versions of the puzzle require that each expression have exactly four fours, but some variations require that each expression have some minimum number of fours.
"Golden ratio base is a non-integer positional numeral system" (2023)
https://news.ycombinator.com/item?id=37969716 :
> What about radix epi*i, or just e?"
> What about radix epi*i, or just e?"
I think I saw this one on an ancient arab math problems book. But it may be apocryphal, not sure how many tools they would have had, factorial symbols?
At any rate they invented algebra so maybe there's something to it
Edit: It was the man who counted, definitely apocryphal, as it was written in the 20th century
At any rate they invented algebra so maybe there's something to it
Edit: It was the man who counted, definitely apocryphal, as it was written in the 20th century
Related numberphile video which goes into a different variation of using all digits in ascending and descending order: https://www.youtube.com/watch?v=-ruC5A9EzzE
but in this case there is a unsolved gap!
but in this case there is a unsolved gap!
So, the formula is really about making any integer with three 2s, but historical precedent calls the game with four 2s more interesting, so the (stronger) result is monkey-patched by replacing a 2 with sqrt(2+2).
Why not use 3 2’s to make n + 2 or n - 2? That’s a lot easier than making a subscript so complicated.
This is the Curse of Knowledge. OP stared too long into the abyss.
This is the Curse of Knowledge. OP stared too long into the abyss.
[deleted]
Wow, it’s been ages since I stumbled upon a math problem that’s not only a blast to solve but also tells a tale! This one’s got it all: easy to grasp, deliciously complex, and comes with a side of drama where some genius totally threw a wrench in the works for everyone else. Bravo!
I like these games, and I would say more fun when using a larger number that has more factors, for example 120. 120 is among the superior highly composite numbers:
https://en.wikipedia.org/wiki/Superior_highly_composite_numb...
https://en.wikipedia.org/wiki/Superior_highly_composite_numb...
[deleted]
I came across a similar video a couple weeks ago about how many ways you can turn a 2 into a 4... https://youtu.be/VEQOv61Gveg
I kinda feel that's cheating and each square root requires a two to use it.
The problem is allowing arbitrary numbers of unary operators. If you allowed ++ increment it would be trivialized even easier. Could even do all complex numbers with only 2 twos.
If you don't allow arbitrary numbers of unary operators and only a finite set of binary operators then you will only be able to represent a finite number of numbers. You need at least one "useful" unary operator for the problem to remain interesting.
Is using a primorial permitted?
7 = (2+2)#+2/2
[deleted]
You don't need the gamma function to get to 7. You can stay at an Algebra 1 level.
I solved the puzzle for 1-10 before looking at the answers, and this was my solution for 7:
⌊√222⌋/2
or more readably:
floor(sqrt(222)) / 2
I solved the puzzle for 1-10 before looking at the answers, and this was my solution for 7:
⌊√222⌋/2
or more readably:
floor(sqrt(222)) / 2
With rounding functions you can get to 7 with just
ceil(2.2)+2+2
ceil(2.2)+2+2
If floor a legitimate mathematical function?
Am I missing something or 7 is simply 2 + 2 + 2 + 2/2?
All those are allowed, so what's the problem?
All those are allowed, so what's the problem?
Your first example uses 2 five times. Your second results in 3
[deleted]
Getting to 7 is notoriously difficult
2 * 2 * 2 - 2/2
This is just Peano arithmetic with extra steps
i thought the famous puzzle was 4, 4s
9 = 22 / 2 - 2
[deleted]
Is 7 really notoriously difficult to define?
7 = 2/2 + 2 + 2 + 2
7 = 2/2 + 2 + 2 + 2
You used five twos.
Thanks—I think we'll merge the comments hither because this submission was the first, and because the other submitter currently has a second article on the frontpage right now.
2/2+2/2…
Then you just add it multiple times
And if 0 is an integer.
2/2-2/2
Then you just add it multiple times
And if 0 is an integer.
2/2-2/2
Doesn’t seem like the author is recursively building solutions, so this doesn’t work.
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.