6 ms·

My Mathematical Regression

366 points by aleda145 4mo ago

ogogmad 3mo ago
me@localhost:~> bc d=1; for(i=21; i < 41; i++){d *= i;}; print d; print "\n"; 335367096786357081410764800000 n = 1; for(i = 1; i < 21; i++){n *= i;}; print n; print "\n"; 2432902008176640000 d/n; 137846528820 I couldn't start Python for some reason, so I went 1337 and used BC, which comes preinstalled in every Unix-like OS. BC has a surprising advantage here since 40!/20! cannot be represented as a 64-bit integer since its value exceeds 2^64. That said, BC's stdlib does not provide the factorial function* - so I had to resort to using for-loops instead. * - What it does contain is sine, cosine, exponential, log, arctan, and Bessel J (?!?!?!?!)
- qsort 3mo ago
  You don't need space for 40!/20!, for example: let ans = 1 for (let i=1; i<21; ++i) { ans *= (41 - i) ans /= i } The same idea can be trivially tweaked to compute any binomial coefficient without ever storing an integer greater than the final result.
  - ogogmad 3mo ago
    Good point. But what if `i` does not divide `ans` evenly? I suppose you could use floats and then round.
    - qsort 3mo ago
      It always divides it evenly, that's why it works. After the i-th iteration of the for loop, ans will contain n!/((n-i)!i!) which is exactly \binom{n}{i}, an integer. Technically "ans" can grow above the final result in my example, but even that could be fixed if one really wants (e.g. i must divide either ans or n-i, you play a bit with divmod to figure out which division you do first.)
- aesthesia 3mo ago
  Just noting that Python natively handles integers larger than the machine word size since version 2.5, so this would have worked in Python as well.
  - ogogmad 3mo ago
    I think BC's features are equivalent to: - Python's native integer handling, which already has no size limit. - PLUS part of the Decimal module in Python's stdlib: BC's floats are DECIMAL by default, not binary. - PLUS an implementation of Bessel's J function, while neglecting Bessel's K. - Some features for base conversion using `ibase` and `obase`. So, I suppose you can output numbers to base 60. [EDIT: Correction from earlier: ibase is allowed to be at most 16, while POSIX allows for the maximum value of obase to be at least 99, which therefore does allow for formatting output to base 60.]
  - Qem 3mo ago
    And does it quite fast too: https://www.wilfred.me.uk/blog/2014/10/20/the-fastest-bigint-in-the-west/ https://www.wilfred.me.uk/blog/2014/10/20/the-fastest-bigint...
mb7733 3mo ago
An intuitive motivation for the solution in the article (2n choose n). For an n*n grid you have to you will take 2n steps, n "over" and n "down". All that matters is the order of the steps. So if you think of there being 2n "slots", you have to pick n to be "over", and the rest are forced to be "down". So it's n choose 2n indeed. You can also think of it another way, without using the formula combinations, and only the fact that there are n! permutations of n objects. We can think of this a permutation of 2n items, made up of two groups of n identical items each. Using (2n!) will overcount, due to the fact that each of the "over" steps are identical, and similarly for the "down" group. We have cut down our answer by dividing out all of the repeated sequences. There will be n! redundancies for all the ways we can permute the "over" group and, the same for the "down" group. So this results in (2n!) / (n! * n!), which is exactly equal to 2n choose n. See [1] which explains permutations with repetion this in general. [Note: We pretty much re-derived the formula for combinations!] [1] https://brilliant.org/wiki/permutations-with-repetition/ https://brilliant.org/wiki/permutations-with-repetition/
- namanyayg 3mo ago
  This was one of my favorite Project Euler problems, but getting to the mathematical solution admittedly took me a couple of weeks. Perhaps because I was pigeon-holing this as a programming optimization problem. I wrote about it too! [0] [0] https://nmn.gl/blog/vibe-coding-gambling https://nmn.gl/blog/vibe-coding-gambling
- xelxebar 3mo ago
  Just noticed this, but intriguingly, Catalan numbers are (2n C n)/(n+1), which hints at a connection with trees. Off the cuff, notice that the diagonal has n+1 intersection points, and a path that never passes through the diagonal gives a forest via the isomorphism with ballot sequences [0]. Any sequence that does pass below the diagonal can be "rotated" into one that doesn't, and so there are probably n+1 paths in each "path class" on average. Conversely, this would suggest that all paths contained in just one upper or lower triangle of the square can be counted by the Catalan numbers. Indeed, a 2x2 square has just 2 such paths and (2n C n)/(n+1) = 6/3 = 2. [0]:https://blog.wilsonb.com/posts/2026-02-27-easy-random-trees.html https://blog.wilsonb.com/posts/2026-02-27-easy-random-trees....
aeve890 3mo ago
Ha. When I found that problem I draw the grids and paths from the example, left for a coffee and when came back I just look at the drawings at an angle and thought "well this is just Pascal's triangle". And the solution was obvious.
the_red_mist 3mo ago
Tbh your student reasoning is still dangerous... the patterns could have not generalized nicely. see moser's circle problem needed to justify viewing this as "arranging down vs right movements" as another comment outlines
floppyd 3mo ago
Noticing a pattern and just extending it without proving why it works is not really a solution. You can prove it without really "understanding" it using induction, but that still would be proof, same as just counting on a computer.
jp57 3mo ago
I think one of the saddest thing is that the kind of person who would recognize, "we can solve this seemingly complicated problem by just applying this formula", would often have trouble even getting recognized in many corporate environments. I managed a guy like that. He was capable of very complex thinking, but he wasn't in love with complexity, he was in love with simplicity. His solutions tended to be of the form, "we can ignore all these things, and just focus on X, and it will provide all the value." He'd notice something and simplify it and the benefit to the company would be measured in multiples of his salary. Every manager who'd ever directly managed him knew what a treasure he was, but it was often hard for us to convince others of the value of his solutions because they were so simple, and people were convinced that hard problems must have complex solutions. (or else they would have solved them, right?) He eventually got bored. He retired and joined a seminary.
- xg15 3mo ago
  I imagine this is where the reputation of a good manager comes in and the ability to say to their boss "hey, we should keep this guy... just trust me on this."
  - adrianN 3mo ago
    If the company runs on reputation it’s only a matter of time until a consultant comes in and processes are established to move to a more efficient metric based management style.
    - wwind123 3mo ago
      Yeah, it's tough either way. Some managers might be biased and keep praising some of their reports that don't actually provide good value for the company. For an outside observer that has no intimate knowledge to the work, how could this be differentiated from the manager having a backbone to support a report that does truly great work but there is no good metric to prove it?
  - mym1990 3mo ago
    Good managers are fairly rare, even though every manager probably thinks they are a good manager.
cocoto 3mo ago
Even if you don’t know or remember the basics of combinatorics you can solve the problem with basic dynamic programming : start with the unit grid and then expend it.
jasonmp85 3mo ago
[dead]
Mainan_Tagonist 3mo ago
The more i think about math these days, the more i see it as a muscle one must constantly train to achieve its potential. Give it too long a rest and you have to go back at full blast for weeks on end to hope to ever achieve past performance. I am very bad at math and have always been in awe of those who can do it well.
- deleted 3mo ago
  [deleted]
purple-leafy 3mo ago
Heh, this grid image is all too familiar to me right now. I’m building a grid based game and engine, and I have a game replay format which is not video. I hit a massive wall with compression, trying to compress unit pathing and was trying to solve a similar solution. Given an NxN grid, and the 4 cardinal directions (NSEW) you can move in, plus an extra action that makes you move 2 cells instead of 1, and considering you can move 4 cells per second… What’s the smallest worst-case raw compression artefact you can output for 1 player for a 1 minute game? It’s an extremely fun problem to solve. I tried: - encoding changes into bits eg using 2 bits for direction - movement pattern batching (ie batching 2 moves into 3 bits) - crowd patterns and movement prediction - treating movement as a “projectile” and deriving intermediate states And all sorts of other wild crap that I will write up about on game launch
- tux3 3mo ago
  What a lot of games do is run a strictly deterministic simulation in lockstep. Then you don't save the path of every unit, you save one move command for the whole group. Then the game replays inputs, and the pathing algorithm should give the same result if there are no desyncs.
  - purple-leafy 3mo ago
    Yes you are definitely onto something! Love to see more people talking about deterministic games. My game is strictly deterministic, so I get bot movement for free - but the player has agency so I need to capture their deviations That’s the tricky part! Right now I do capture input (actually just deviations) and can replay whole games, but I think I’m at the limits in terms of compression - talking bytes here not KB
    - AlotOfReading 3mo ago
      How much did your clever approach save over a naive approach + file compression?
      - 3mo ago
aesthesia 3mo ago
I've had the same experience looking back at solutions to old problem sets and wondering how I ever came up with them.
d_silin 3mo ago
Nobody forces you to use AI. It has become sort of junk food for the brain. Temptations and ads for it everywhere.
- bluefirebrand 3mo ago
  If you have performance based metrics about your AI usage then you are essentially being forced to use AI (or become unemployed) Plenty of people are experiencing this nowadays The idea that no one is being forced to use AI is nonsense
  - pocksuppet 3mo ago
    That was in the first calendar quarter this year. In the second calendar quarter CEOs started saying AI is too fucking expensive and let's stop doing it.
    - chatmasta 3mo ago
      You’re now being forced to optimize your AI cost usage and produce the same results as before you cared about it.
    - RugnirViking 3mo ago
      maybe your C suite. ours just joined the hype train. We got an email a few weeks ago saying all new code must be ai generated by 2027 and introducing internal metrics for ai usage by team
  - d_silin 3mo ago
    There is no metric a reasonably intelligent person can't sabotage or subvert... ...for example, you can write a script to burn tokens and write the code yourself.
    - degamad 3mo ago
      e.g. <https://github.com/dtnewman/burn-baby-burn https://github.com/dtnewman/burn-baby-burn>
rabbitlord 3mo ago
More like mathematical depression.
dhosek 3mo ago
There’s a bit of hand-waving in the jump to 2n choose n solution, which I suppose is fine, and my ex–math teacher brain really wants to have a proper proof or at least solid reasoning rather than “it follows the pattern” based on three observations. But I am reminded of how during my engagement 24 years ago, my future father-in-law raised an issue of being able to determine whether they were getting the full amount of sandpaper on large rolls that they were paying for. I was able to simplify the question a bit to one that treated the rolls as if they were simple concentric rolls of a specified thickness and from there could turn it into the good old Gaussian sum formula times 2π to get the length. The engineers working for the company came up with the same solution, but instead of using n(n-1)/2 they did the summation with multiple rows in excel.
- shenberg 3mo ago
  You always either go left or down so total 40 steps, choose 20 to be down (or 20 to be right)
  - dhosek 3mo ago
    Which suggests another approach to the solution; you have 20Ls and 20Rs which can appear in any order so it’s a permutation with repetition problem and thus 40!/(20!20!) That approach has the advantage that it’s easily adapted to non square rectangular grids (n+m)!/(n!m!)
- gobdovan 3mo ago
  You can go down or right at any point. To go in bottom-right corner, you need n down steps and n right steps. In how many ways can you arrange n things on type A and n things of type B? In C(2n, n). The problem is about modeling, once you model it correctly, you get the definition of combinations.
  - dhosek 3mo ago
    C(2n, n) isn’t about permutations, but choosing subsets of a set without order, but as I’ve thought about it, the model here is that there are 2n moves to be made and you need to choose n of them to be down (or right, depending on your preference).
utopiah 3mo ago
Comment as a song https://mariedavidson.bandcamp.com/album/work-it-soulwax-remix https://mariedavidson.bandcamp.com/album/work-it-soulwax-rem... There is no easy way out, you have to rest but you simply can't stop. Your body will rot, your mind too. PS: song isn't an ode to the grind culture or how to slave away in an office, as lyrics say "you’ve got to work for yourself - Love yourself, feed yourself".
krackers 3mo ago
"Compute the first few terms and plug into OEIS" is very high on the reward:effort scale
- nullc 3mo ago
  Came here to say this-- I've solved a lot of otherwise seemingly quite hard problems by numerically/brute-force finding the first few terms then asking OEIS then convincing myself it it's indeed the solution.
- utopcell 3mo ago
  not really solving the problem though. would be easier to directly search for project euler xx solution.
andredurao 3mo ago
That Project Euler problem was my first encounter with memoization. At the time, it felt like a magical solution, so I ended up solving it using the central column of Pascal's triangle, which was easier for me to understand back then. I also tried a weird idea involving popcount, but it didn't scale. My approach was to represent each possible path with 0s (don't turn) and 1s (turn), testing the same number of 0s and 1s. However, even with popcount running in O(1) with hardware support, the total number of possible paths made the idea impractical :)
- chatmasta 3mo ago
  The binomial coefficient is derived from Pascal’s triangle, which is a fact I remember but cannot explain, based on some hazy memories of 10th grade math class.
  - zmgsabst 3mo ago
    You can take the two variables to be outcomes of a binomial event: - at zero events: we have one outcome, nothing - at one event: we have two outcomes, 1X and 1Y - at two events, each of those two outcomes have two outcomes, but one X and one Y outcome both become XY, so we have 1X^2 2XY 1Y^2. You can continue combining this way, adding an X and Y to each term (for the two possible outcomes) — and then grouping like terms.
kccqzy 3mo ago
I was sad in a different way. I immediately realized that this could be solved by dynamic programming by computing the recurrence F(x,y)=F(x-1,y)+F(x,y-1) with the base case F(0,0)=1 and F(x,y)=0 if x<0 or y<0. The problem is that I immediately jumped to generating functions as a tool to solve this. I defined G(u,v)=\sum_x \sum_y F(x,y) u^x v^y. After maybe ten minutes of manipulation I arrived at the closed form for G(u,v)=1/(1-u-v). At this point I recognized its series expansion and its coefficients are just given by the binomial theorem. I feel sad because I had forgotten the simple and intuitive construction of choosing “go down” and “go right” directions. When a person learns more advanced mathematics, it is often the case that the person just applies such advanced mathematics by rote without realizing that a solution can be found with more elementary mathematics and more creativity. It reminded me of the time in middle school before derivatives were taught, when my teacher reminded me that using derivatives to solve a problem would receive no credit.
- srean 3mo ago
  There is nothing wrong in using generating functions. A very handy and powerful tool. I wish I was better at it than I am. It is a common experience in mathematical problem solving that the first solution leads to more insight which illuminates a shorter slap-my-forehead solution -- bruised forehead.
gobdovan 3mo ago
This is a pre-AI phenomena. I observe it quite a lot with stuff I did in high school but usually with complex problems. What's generally happening is that you were working with pen and paper through a hard problem. With adult brain, you'd expect just to know the answers, but in reality you're not much smarter than you were at 14, so you need to do the thing properly. Also if you help little kids with homework, you'll see that some problems are quite difficult as well and require you to actually think, even if it's problems for 10 year olds.
- ForOldHack 3mo ago
  Yes, AI can write a solution, but cannot visualized a solution. When I was 9, I refused to learn my times tables, and addition, so I was relegated to work with blocks. I loved the blocks... I was able to complete all the problems, come up with my own, and return to class, with some extreme facility. Two years later, comes a challenge in class... make a formula for summing the integers... well everyone started with 1+2+... I starred with blocks, 1+n, 2+n-1... I had the complete formula in minutes... That was the very last class for which I was with my peers of that grade... I was put in a HP High Potential class, with a high school algebra book, and although was a bit lonely, was in my element. The point is- the recognition of the problem, can save huge amounts of time, where as AI can only brute force it, or use a pretrained solution.
  - eru 3mo ago
    Eh, AI is getting better at creating little visualisations, too.
  - tkfoss 3mo ago
    are block referring to Cuisenaire rods?
johndough 3mo ago
Another approach that often works for these kinds of problems and does not require much intelligence: Work out the first few cases by hand (1,2,6,20 in our case) and then look up the sequence on "The On-Line Encyclopedia of Integer Sequences" (OEIS): https://oeis.org/search?q=1%2C2%2C6%2C20&language=english&go=Search https://oeis.org/search?q=1%2C2%2C6%2C20&language=english&go...
vm64 3mo ago
We taught this problem in my college’s discrete math course. The intuition we gave is that it’s exactly equivalent to the number of ways to rearrange a string of 20 Rs and 20 Ds (corresponding to a right and down move)
hiAndrewQuinn 3mo ago
The trick to making these problems intuitive is to mentally rewrite them into a "how many permutations of this string are possible?" problem. Consider the 2 * 3 case. ... ... One way you might get there is Right, right, right, down, down Then you can rewrite this as RRRDD You will always need 3 R's, and you will always need 2 D's. So how many unique strings can be made with this? Well let's actually consider the degenerate cases. ABCDE there are 5 places A can go, then 4 left B can go, then 3 left C can go, and so on, until we get 5! = 120 possible permutations of ABCDE. If you replace the B with another A to get AACDE now there are only 60 permutations, because half of the original 120 only differed by where the A and the B were relative to one another. By that same logic, AACCE has only 30 combinations, and AACCC has only 10 (seeing why it's 10 and not 20 is actually the trickiest part imo, it's because there are 3! ways to arrange CDE, but only 1 to arrange CCC). AACCC is isomorphic to RRDDD, which is how we get 10 possible paths to solve the 2*3 grid. We can check this with the binomial theorem: ((2+3) choose 3) = 10. What's nice about this step by step approach is that it generalizes not just to non-square grids, but to multiple dimensions as well! Imagine trying to get from the top of a 3 by 3 by 3 Rubik's cube to the bottom, how do you do that? Well how many ways are there to rewrite AAABBBCCC ? The logic above would suggest 9! / (3! 3! 3!) = 1,680 unique paths. And you can just derive it by starting from the degenerate case and figuring out how to slice things up!
soseng 3mo ago
This is also me. I was a double CS and Math major in university and one of my favorite classes as a young lad was combinatorics and probability.. 25 years ago.. It's true, if you don't activate this area of your brain often, it's easier to brute force the solution and reach for the easy mechanical calculation. I can feel this when I'm refactoring code. Today, I just have Claude do it for me with a few instructions. Each day, I feel a tiny bit more ignorant about the actual framework's APIs, its abstractions, and its rules. But I still would rather do other things with my time. As for the problem, luckily for me, this one was easy to derive if you remember factorials, permutations, and remember to account for duplicate patterns
bmenrigh 3mo ago
The 2n choose n solution isn't at all intuitive to me but thinking about it in terms of 40 steps, 20 of them rightward and 20 of them downward an then looking at all distinct permutations of these 40 steps as (40!) / ((20!)^2) is intuitive to me. Then it becomes obvious that since 20 is half of 40, k and n - k are the same number (20), which coincides with the binomial coefficient n! / k!(n - k)!. But this seems like a lucky coincidence in 2 dimensions and if you extended the problem into 3D you'd do better thinking about permutations.
- emil-lp 3mo ago
  2n choose n is just: you must move East 20 times and South 20 times. Hence any solution looks like a permutation of 20 Es and 20 Ss. Now, only look at the indices for the Es. There are 20 of them. Out of 40. 40 indices, pick 20. Those are East moves, the rest are South moves.
  - grumbelbart2 3mo ago
    This interpretation also generalizes nicely to 3d. You have 60 moves, 20 of which will be up (60 choose 20), then 20 are east (40 choose 20), then 20 are south (20 choose 20).
    - C-x_C-f 3mo ago
      That's a nice way to put it. FWIW the generalization of binomial coefficient which allows you to express an n-dimensional solution is called a multinomial coefficient [0]. So in a 3d 20x20x20 box we would have (60 multichoose 20, 20, 20) paths. Also, the wiki article doesn't mention this but the growth rate of (n multichoose k1, k2, ..., km) as we increase n but fix the ratios p1 = k1 / n, ..., pm = km / n is precisely the Shannon entropy of the categorical distribution with probabilities p1, ..., pm . The wiki article for entropy [1] states the result for the binomial coefficient, which can be written as (n choose k) = (n multichoose k, (n - k)) . Actually a lot of basic information-theoretic results about entropy and related quantities (e.g. the properties of the Boltzmann distribution/softmax function) can be derived from similar discrete counting problems after taking a large-n limit. I don't have links at the ready but I might edit this comment if I remember places which explain this stuff. [0] https://en.wikipedia.org/wiki/Multinomial_theorem#Number_of_unique_permutations_of_words https://en.wikipedia.org/wiki/Multinomial_theorem#Number_of_... [1] https://en.wikipedia.org/wiki/Entropy_(information_theory)#Approximation_to_binomial_coefficient https://en.wikipedia.org/wiki/Entropy_(information_theory)#A...
meindnoch 3mo ago
Manhattan distance is 2n steps. Of these, exactly n are to the right, the rest is downwards. A 2n step path is completely determined by choosing which n steps will be to the right. Hence 2n choose n. This is high school math.
Imustaskforhelp 3mo ago
I am currently just going to college after high school and I was preparing for the JEE exam and I remember such a question was within the textbooks of maths itself. At first glance of the question, I had imagined it to be hard but then I read through the solution and other comments to recognize that I had in fact done such a question previously and I had solved it independently during the class if I remember correctly or such classes of problems. I also agree with the AI and spreadsheets part of thing for what its worth but I can only tell more when I get into job but I have heard such things from my senior brothers. I feel like there has to be a right balance of complexity though, and for what its worth I think that there are so many other things that one optimizes later on in life with tangential benefits as well with real knowledge about real life use-cases and edge-cases and so much more! I feel like it would be hard to replace with AI as much as (some) people (mostly Marketing) want it to feel so. I do hope that people don't atrophy their skills though and to solve some coding questions or make projects perhaps as well without LLM by hand if given/having the time. Not everything probably has to be done by the fastest or the most accelerated way as you wouldn't know the destination as it would be found along the way itself. I suppose just like life, so stay safe and have a nice day.
blmarket 3mo ago
I think it's due to calibration - practical work related problems are never that simple & easy so naturally people might start from DP formula. D[A,B] := number of ways to navigate from grid sized AxB = D[A-1,B]+D[A,B-1] and the aha moment is realising this is just a binomial coefficient.
vatsachak 3mo ago
This is why you still work on open source and do coursework for fun. The same reason you go for a jog
shshsjsj 3mo ago
this is like the most basic leetcode question. Some comments here sound like they need to brush up the basics
- utopcell 3mo ago
  thanks for keeping us honest. what would we ever do without this insightful comment of yours?
Sharlin 3mo ago
If you want to keep your math brain working, and to find use for any and all the math you learned in school, look no further than graphics programming.
jldugger 3mo ago
Project Euler is like this a lot -- it's presented as a coding challenge but half the problems can be optimized to return 5 # because math
- Jtsummers 3mo ago
  At least the site itself is honest about it, describing the challenges as "mathematical/computer programming problems". I always found it weird when people recommended them as ways to learn a new programming language because, perhaps because of my own math background, I ended up solving most of them with math and so little programming. Where the programs only used the basics of any language so that nothing novel would be learned by rewriting except for how loops look in two different languages (or don't, in the case of some FP languages), or how arrays look, etc.
totetsu 3mo ago
I have to say the youtube algorhythm has done wonders from my mathmatical ability by directing me to so much numberphile and 3Blue1Brown etc. And rapid AI prototyping of ideas involving complex maths has really helped me build and check intuitions about things that i might never have made if I got stuck in the weeds of trying to understand it all from 0. Like oh if this works in 2 dimensions I wonder how it looks in 4. 4d connect 4 is quite a fun game.
SilverSlash 3mo ago
I can definitely relate. My brain also wants to take the path of least effort now, even for simple things like adding two numbers which I could do very quickly in my head in my college days. And with AI the path of least (initial) effort seems to be to just ask the model to solve it. It might get it wrong and then I'll prompt it again and again. But each individual prompt is fairly low effort on my part. Whereas coming up with the right solution myself might've taken less time but the initial effort is a lot more. Last year I used to romanticize about building at least 1 thing each month completely by hand without any LLM coding help. The last such project I worked on was 6 months ago so sadly it's not going so well.
markus_zhang 3mo ago
I could be wrong but I feel this solution is not proved to be correct, but could be nevertheless the answer. On the other side, my Math ability definitely goes down to Calculus and I definitely forgot most about geometry.
noosphr 3mo ago
All problems in project Euler have closed form solutions. The computer programming part of it is just a quick way to develop candidate solutions.
- iwsk 3mo ago
  https://projecteuler.net/problem=76 https://projecteuler.net/problem=76 does this have a closed form solution? vast majority of the problems don't seem to have a closed form solution
abetusk 3mo ago
I appreciate where the author is coming from, as we often have much more context because of training that have since atrophied a bit, but in defense of the dynamic programming solution, this generalizes very well. As stated, the choose(2n,n) solution of course works but as soon as you deviate from a square, things can get more complicated. What if it's a rectangle? An arbitrary shape? One with holes? The dynamic programming solution takes all of this in stride (assuming, of course, that the conditions of only going right and down still hold). Pascal's triangle is, after all, a dynamic programming solution. It just so happens that there's a "closed form" solution to their entries. I'm all for clever tricks but I also appreciate much more a solution that generalizes well and gives more insight into a class of problems.
- Skeime 3mo ago
  The rectangle case is just choose(w+h, h), with w, h being the width and height, respectively. (Or choose(w+h, w), which is the same.) Depending on how well you know binomial coefficients, this can also lead you to the dynamic programming solution. After all, for the rectangle case this is nothing but construction of Pascal's triangle by summing two adjacent numbers in a row to get the number below them. If you recognize this, the solution for paths on grids with holes falls out almost immediately.
dominicrose 3mo ago
Even for a math teacher the math isn't the hard part of the job.
GL26 3mo ago
The way the problem was solved at first hand by just "recognizing the pattern of (2n) choose n" wouldn't satisfy me at all, where's the proof ? Why does it work ? This isn't maths, this is "pattern recognition".
- igsomething 3mo ago
  Maths IS pattern recognition
  - BeetleB 3mo ago
    Followed by a proof via induction.
- pillmillipedes 3mo ago
  in math it's often the case that you notice the solution first and only afterwards prove to yourself that it works. pattern matching and intuition play a large role in math! this is why I'm not a big fan of "show your work": the "work" is however many years it took to build up my intuition, and often any explanation I could type out for my solution would be a retroactive rationalization. it's still useful, sure -especially for catching your errors, but I place it on the opposite end of the open-fake scale than most people. of course here the proof is simple: 20 right moves, 20 down moves, any order => of 40 total moves choose any 20 indices to be your down moves => 40 choose 20 is your answer. would that teach you how to solve the next problem though? I'm not so sure.
a_c 3mo ago
Don't worry, we can regress our programming skill after 6 months of management, management of agents I mean
ramon156 3mo ago
> this is just me fantasizing. At work I would just give it to an AI and continue with my day I'm sure ~4 yrs ago i would have loved the thought of this. It's so boring. My job is so, so boring.
deleted 3mo ago
[deleted]
storus 3mo ago
I noticed the same with me after a few years working; my solution was to take all hard mathy online MS degrees/grad certs available one after the another. Now I can understand how does the generative AI math work while designing an electric motor for my own robot. Though the latest AI can do it all better than me.
jadar 3mo ago
Yeah, this is relatable. Part of it comes down to "use it or lose it." We atrophy when we don't exercise. But at the same time, it might come back to the OP faster than he thinks if he went into it. Also, I've found that with AI I'm able to ask specific questions where I'm hazy and pick things up faster than if I just had to watch hours of lectures to pick something up. (There's a place for both.)
erdaniels 3mo ago
Since I'm between jobs, I've been taking the time to relearn geometry, trig, calc, and linear algebra. I've finished the first two and it's both humiliating and really fun to relearn some math. As an adult, I feel a very different appreciation for how much fundamental math we take for granted. I definitely recommend https://www.khanacademy.org/ https://www.khanacademy.org/ and pauls notes (https://tutorial.math.lamar.edu/ https://tutorial.math.lamar.edu/).
jerf 3mo ago
Something I haven't seen anyone else mention is that this is problem 15. The author probably did the previous 14 problems too. IIRC the problems aren't strictly cumulative but you do generally end up warmed up and with hints about how to approach problem N efficiently from problems [1, N-1]. Skills do decay, I can't deny that. But even when I was still in school going back and doing an end-of-year problem for a class I took two years ago would have been harder than it was for me at the time... but it would have been easier than the first time if I warmed up properly with a bit of review and practice first, and I mean, not just three minutes glancing over things but taking some serious time for it.
- esterna 3mo ago
  The sequence numbers of problems on Project Euler only represent the order of publication. They aren't deliberately connected except for a few problems that have one or two follow-ups. Most of the first 100 problems can be solved without any understanding of the problem, should you so desire.
1970-01-01 3mo ago
Because the daily world has much less math in it than we care to admit. You don't need calculus to understand which elevator button needs to be pushed.
gradientsrneat 3mo ago
Professional mathematicians and computer scientists use AI as well. Maybe that's not very reassuring from the standpoint of skills regression in modern adult work culture, but at least it demonstrates that skills and tool usage aren't mutually exclusive.
helpfulfrond 3mo ago
A lot of life is "use it or lose it," due to limited resources I imagine.
Martins000 3mo ago
[dead]
lajarre 3mo ago
i often hear this frustration, been hit by it first-hand and am just recovering my keys to overcoming this frustration: * capture (focus on) the joy of doing math; this doesn't get better the more you know (i'd argue, to the contrary); a child figuring out that 2+2 = 3+1 is as profoundly moved as Tao doing his most advanced ones * be responsible and figure out what parts of the maths journey have lastingly influenced your way of thinking about the world; if you trust math is really beautiful or "it's the language of the universe" or something, then it _must_ have an influence on how you see things; not because of the theorems, but because of the practice; isolate this, nurture it

366 points by aleda145 4mo ago

me@localhost:~> bc d=1; for(i=21; i < 41; i++){d *= i;}; print d; print "\n"; 335367096786357081410764800000 n = 1; for(i = 1; i < 21; i++){n *= i;}; print n; print "\n"; 2432902008176640000 d/n; 137846528820 I couldn't start Python for some reason, so I went 1337 and used BC, which comes preinstalled in every Unix-like OS. BC has a surprising advantage here since 40!/20! cannot be represented as a 64-bit integer since its value exceeds 2^64. That said, BC's stdlib does not provide the factorial function* - so I had to resort to using for-loops instead. * - What it does contain is sine, cosine, exponential, log, arctan, and Bessel J (?!?!?!?!)

qsort 3mo ago
You don't need space for 40!/20!, for example: let ans = 1 for (let i=1; i<21; ++i) { ans *= (41 - i) ans /= i } The same idea can be trivially tweaked to compute any binomial coefficient without ever storing an integer greater than the final result.
- ogogmad 3mo ago
  Good point. But what if `i` does not divide `ans` evenly? I suppose you could use floats and then round.
  - qsort 3mo ago
    It always divides it evenly, that's why it works. After the i-th iteration of the for loop, ans will contain n!/((n-i)!i!) which is exactly \binom{n}{i}, an integer. Technically "ans" can grow above the final result in my example, but even that could be fixed if one really wants (e.g. i must divide either ans or n-i, you play a bit with divmod to figure out which division you do first.)
aesthesia 3mo ago
Just noting that Python natively handles integers larger than the machine word size since version 2.5, so this would have worked in Python as well.
- ogogmad 3mo ago
  I think BC's features are equivalent to: - Python's native integer handling, which already has no size limit. - PLUS part of the Decimal module in Python's stdlib: BC's floats are DECIMAL by default, not binary. - PLUS an implementation of Bessel's J function, while neglecting Bessel's K. - Some features for base conversion using `ibase` and `obase`. So, I suppose you can output numbers to base 60. [EDIT: Correction from earlier: ibase is allowed to be at most 16, while POSIX allows for the maximum value of obase to be at least 99, which therefore does allow for formatting output to base 60.]
- Qem 3mo ago
  And does it quite fast too: https://www.wilfred.me.uk/blog/2014/10/20/the-fastest-bigint-in-the-west/ https://www.wilfred.me.uk/blog/2014/10/20/the-fastest-bigint...

mb7733 3mo ago

An intuitive motivation for the solution in the article (2n choose n). For an n*n grid you have to you will take 2n steps, n "over" and n "down". All that matters is the order of the steps. So if you think of there being 2n "slots", you have to pick n to be "over", and the rest are forced to be "down". So it's n choose 2n indeed. You can also think of it another way, without using the formula combinations, and only the fact that there are n! permutations of n objects. We can think of this a permutation of 2n items, made up of two groups of n identical items each. Using (2n!) will overcount, due to the fact that each of the "over" steps are identical, and similarly for the "down" group. We have cut down our answer by dividing out all of the repeated sequences. There will be n! redundancies for all the ways we can permute the "over" group and, the same for the "down" group. So this results in (2n!) / (n! * n!), which is exactly equal to 2n choose n. See [1] which explains permutations with repetion this in general. [Note: We pretty much re-derived the formula for combinations!] [1] https://brilliant.org/wiki/permutations-with-repetition/ https://brilliant.org/wiki/permutations-with-repetition/

namanyayg 3mo ago
This was one of my favorite Project Euler problems, but getting to the mathematical solution admittedly took me a couple of weeks. Perhaps because I was pigeon-holing this as a programming optimization problem. I wrote about it too! [0] [0] https://nmn.gl/blog/vibe-coding-gambling https://nmn.gl/blog/vibe-coding-gambling
xelxebar 3mo ago
Just noticed this, but intriguingly, Catalan numbers are (2n C n)/(n+1), which hints at a connection with trees. Off the cuff, notice that the diagonal has n+1 intersection points, and a path that never passes through the diagonal gives a forest via the isomorphism with ballot sequences [0]. Any sequence that does pass below the diagonal can be "rotated" into one that doesn't, and so there are probably n+1 paths in each "path class" on average. Conversely, this would suggest that all paths contained in just one upper or lower triangle of the square can be counted by the Catalan numbers. Indeed, a 2x2 square has just 2 such paths and (2n C n)/(n+1) = 6/3 = 2. [0]:https://blog.wilsonb.com/posts/2026-02-27-easy-random-trees.html https://blog.wilsonb.com/posts/2026-02-27-easy-random-trees....

aeve890 3mo ago

Ha. When I found that problem I draw the grids and paths from the example, left for a coffee and when came back I just look at the drawings at an angle and thought "well this is just Pascal's triangle". And the solution was obvious.

the_red_mist 3mo ago

Tbh your student reasoning is still dangerous... the patterns could have not generalized nicely. see moser's circle problem needed to justify viewing this as "arranging down vs right movements" as another comment outlines

floppyd 3mo ago

Noticing a pattern and just extending it without proving why it works is not really a solution. You can prove it without really "understanding" it using induction, but that still would be proof, same as just counting on a computer.

jp57 3mo ago

I think one of the saddest thing is that the kind of person who would recognize, "we can solve this seemingly complicated problem by just applying this formula", would often have trouble even getting recognized in many corporate environments. I managed a guy like that. He was capable of very complex thinking, but he wasn't in love with complexity, he was in love with simplicity. His solutions tended to be of the form, "we can ignore all these things, and just focus on X, and it will provide all the value." He'd notice something and simplify it and the benefit to the company would be measured in multiples of his salary. Every manager who'd ever directly managed him knew what a treasure he was, but it was often hard for us to convince others of the value of his solutions because they were so simple, and people were convinced that hard problems must have complex solutions. (or else they would have solved them, right?) He eventually got bored. He retired and joined a seminary.

xg15 3mo ago
I imagine this is where the reputation of a good manager comes in and the ability to say to their boss "hey, we should keep this guy... just trust me on this."
- adrianN 3mo ago
  If the company runs on reputation it’s only a matter of time until a consultant comes in and processes are established to move to a more efficient metric based management style.
  - wwind123 3mo ago
    Yeah, it's tough either way. Some managers might be biased and keep praising some of their reports that don't actually provide good value for the company. For an outside observer that has no intimate knowledge to the work, how could this be differentiated from the manager having a backbone to support a report that does truly great work but there is no good metric to prove it?
- mym1990 3mo ago
  Good managers are fairly rare, even though every manager probably thinks they are a good manager.

cocoto 3mo ago

Even if you don’t know or remember the basics of combinatorics you can solve the problem with basic dynamic programming : start with the unit grid and then expend it.

jasonmp85 3mo ago

[dead]

Mainan_Tagonist 3mo ago

The more i think about math these days, the more i see it as a muscle one must constantly train to achieve its potential. Give it too long a rest and you have to go back at full blast for weeks on end to hope to ever achieve past performance. I am very bad at math and have always been in awe of those who can do it well.

deleted 3mo ago
[deleted]

purple-leafy 3mo ago

Heh, this grid image is all too familiar to me right now. I’m building a grid based game and engine, and I have a game replay format which is not video. I hit a massive wall with compression, trying to compress unit pathing and was trying to solve a similar solution. Given an NxN grid, and the 4 cardinal directions (NSEW) you can move in, plus an extra action that makes you move 2 cells instead of 1, and considering you can move 4 cells per second… What’s the smallest worst-case raw compression artefact you can output for 1 player for a 1 minute game? It’s an extremely fun problem to solve. I tried: - encoding changes into bits eg using 2 bits for direction - movement pattern batching (ie batching 2 moves into 3 bits) - crowd patterns and movement prediction - treating movement as a “projectile” and deriving intermediate states And all sorts of other wild crap that I will write up about on game launch

tux3 3mo ago
What a lot of games do is run a strictly deterministic simulation in lockstep. Then you don't save the path of every unit, you save one move command for the whole group. Then the game replays inputs, and the pathing algorithm should give the same result if there are no desyncs.
- purple-leafy 3mo ago
  Yes you are definitely onto something! Love to see more people talking about deterministic games. My game is strictly deterministic, so I get bot movement for free - but the player has agency so I need to capture their deviations That’s the tricky part! Right now I do capture input (actually just deviations) and can replay whole games, but I think I’m at the limits in terms of compression - talking bytes here not KB
  - AlotOfReading 3mo ago
    How much did your clever approach save over a naive approach + file compression?
    - 3mo ago

aesthesia 3mo ago

I've had the same experience looking back at solutions to old problem sets and wondering how I ever came up with them.

d_silin 3mo ago

Nobody forces you to use AI. It has become sort of junk food for the brain. Temptations and ads for it everywhere.

bluefirebrand 3mo ago
If you have performance based metrics about your AI usage then you are essentially being forced to use AI (or become unemployed) Plenty of people are experiencing this nowadays The idea that no one is being forced to use AI is nonsense
- pocksuppet 3mo ago
  That was in the first calendar quarter this year. In the second calendar quarter CEOs started saying AI is too fucking expensive and let's stop doing it.
  - chatmasta 3mo ago
    You’re now being forced to optimize your AI cost usage and produce the same results as before you cared about it.
  - RugnirViking 3mo ago
    maybe your C suite. ours just joined the hype train. We got an email a few weeks ago saying all new code must be ai generated by 2027 and introducing internal metrics for ai usage by team
- d_silin 3mo ago
  There is no metric a reasonably intelligent person can't sabotage or subvert... ...for example, you can write a script to burn tokens and write the code yourself.
  - degamad 3mo ago
    e.g. <https://github.com/dtnewman/burn-baby-burn https://github.com/dtnewman/burn-baby-burn>

rabbitlord 3mo ago

More like mathematical depression.

dhosek 3mo ago

There’s a bit of hand-waving in the jump to 2n choose n solution, which I suppose is fine, and my ex–math teacher brain really wants to have a proper proof or at least solid reasoning rather than “it follows the pattern” based on three observations. But I am reminded of how during my engagement 24 years ago, my future father-in-law raised an issue of being able to determine whether they were getting the full amount of sandpaper on large rolls that they were paying for. I was able to simplify the question a bit to one that treated the rolls as if they were simple concentric rolls of a specified thickness and from there could turn it into the good old Gaussian sum formula times 2π to get the length. The engineers working for the company came up with the same solution, but instead of using n(n-1)/2 they did the summation with multiple rows in excel.

shenberg 3mo ago
You always either go left or down so total 40 steps, choose 20 to be down (or 20 to be right)
- dhosek 3mo ago
  Which suggests another approach to the solution; you have 20Ls and 20Rs which can appear in any order so it’s a permutation with repetition problem and thus 40!/(20!20!) That approach has the advantage that it’s easily adapted to non square rectangular grids (n+m)!/(n!m!)
gobdovan 3mo ago
You can go down or right at any point. To go in bottom-right corner, you need n down steps and n right steps. In how many ways can you arrange n things on type A and n things of type B? In C(2n, n). The problem is about modeling, once you model it correctly, you get the definition of combinations.
- dhosek 3mo ago
  C(2n, n) isn’t about permutations, but choosing subsets of a set without order, but as I’ve thought about it, the model here is that there are 2n moves to be made and you need to choose n of them to be down (or right, depending on your preference).

utopiah 3mo ago

Comment as a song https://mariedavidson.bandcamp.com/album/work-it-soulwax-remix https://mariedavidson.bandcamp.com/album/work-it-soulwax-rem... There is no easy way out, you have to rest but you simply can't stop. Your body will rot, your mind too. PS: song isn't an ode to the grind culture or how to slave away in an office, as lyrics say "you’ve got to work for yourself - Love yourself, feed yourself".

krackers 3mo ago

"Compute the first few terms and plug into OEIS" is very high on the reward:effort scale

nullc 3mo ago
Came here to say this-- I've solved a lot of otherwise seemingly quite hard problems by numerically/brute-force finding the first few terms then asking OEIS then convincing myself it it's indeed the solution.
utopcell 3mo ago
not really solving the problem though. would be easier to directly search for project euler xx solution.

andredurao 3mo ago

That Project Euler problem was my first encounter with memoization. At the time, it felt like a magical solution, so I ended up solving it using the central column of Pascal's triangle, which was easier for me to understand back then. I also tried a weird idea involving popcount, but it didn't scale. My approach was to represent each possible path with 0s (don't turn) and 1s (turn), testing the same number of 0s and 1s. However, even with popcount running in O(1) with hardware support, the total number of possible paths made the idea impractical :)

chatmasta 3mo ago
The binomial coefficient is derived from Pascal’s triangle, which is a fact I remember but cannot explain, based on some hazy memories of 10th grade math class.
- zmgsabst 3mo ago
  You can take the two variables to be outcomes of a binomial event: - at zero events: we have one outcome, nothing - at one event: we have two outcomes, 1X and 1Y - at two events, each of those two outcomes have two outcomes, but one X and one Y outcome both become XY, so we have 1X^2 2XY 1Y^2. You can continue combining this way, adding an X and Y to each term (for the two possible outcomes) — and then grouping like terms.

kccqzy 3mo ago

I was sad in a different way. I immediately realized that this could be solved by dynamic programming by computing the recurrence F(x,y)=F(x-1,y)+F(x,y-1) with the base case F(0,0)=1 and F(x,y)=0 if x<0 or y<0. The problem is that I immediately jumped to generating functions as a tool to solve this. I defined G(u,v)=\sum_x \sum_y F(x,y) u^x v^y. After maybe ten minutes of manipulation I arrived at the closed form for G(u,v)=1/(1-u-v). At this point I recognized its series expansion and its coefficients are just given by the binomial theorem. I feel sad because I had forgotten the simple and intuitive construction of choosing “go down” and “go right” directions. When a person learns more advanced mathematics, it is often the case that the person just applies such advanced mathematics by rote without realizing that a solution can be found with more elementary mathematics and more creativity. It reminded me of the time in middle school before derivatives were taught, when my teacher reminded me that using derivatives to solve a problem would receive no credit.

srean 3mo ago
There is nothing wrong in using generating functions. A very handy and powerful tool. I wish I was better at it than I am. It is a common experience in mathematical problem solving that the first solution leads to more insight which illuminates a shorter slap-my-forehead solution -- bruised forehead.

gobdovan 3mo ago

This is a pre-AI phenomena. I observe it quite a lot with stuff I did in high school but usually with complex problems. What's generally happening is that you were working with pen and paper through a hard problem. With adult brain, you'd expect just to know the answers, but in reality you're not much smarter than you were at 14, so you need to do the thing properly. Also if you help little kids with homework, you'll see that some problems are quite difficult as well and require you to actually think, even if it's problems for 10 year olds.

ForOldHack 3mo ago
Yes, AI can write a solution, but cannot visualized a solution. When I was 9, I refused to learn my times tables, and addition, so I was relegated to work with blocks. I loved the blocks... I was able to complete all the problems, come up with my own, and return to class, with some extreme facility. Two years later, comes a challenge in class... make a formula for summing the integers... well everyone started with 1+2+... I starred with blocks, 1+n, 2+n-1... I had the complete formula in minutes... That was the very last class for which I was with my peers of that grade... I was put in a HP High Potential class, with a high school algebra book, and although was a bit lonely, was in my element. The point is- the recognition of the problem, can save huge amounts of time, where as AI can only brute force it, or use a pretrained solution.
- eru 3mo ago
  Eh, AI is getting better at creating little visualisations, too.
- tkfoss 3mo ago
  are block referring to Cuisenaire rods?

johndough 3mo ago

Another approach that often works for these kinds of problems and does not require much intelligence: Work out the first few cases by hand (1,2,6,20 in our case) and then look up the sequence on "The On-Line Encyclopedia of Integer Sequences" (OEIS): https://oeis.org/search?q=1%2C2%2C6%2C20&language=english&go=Search https://oeis.org/search?q=1%2C2%2C6%2C20&language=english&go...

vm64 3mo ago

We taught this problem in my college’s discrete math course. The intuition we gave is that it’s exactly equivalent to the number of ways to rearrange a string of 20 Rs and 20 Ds (corresponding to a right and down move)

hiAndrewQuinn 3mo ago

The trick to making these problems intuitive is to mentally rewrite them into a "how many permutations of this string are possible?" problem. Consider the 2 * 3 case. ... ... One way you might get there is Right, right, right, down, down Then you can rewrite this as RRRDD You will always need 3 R's, and you will always need 2 D's. So how many unique strings can be made with this? Well let's actually consider the degenerate cases. ABCDE there are 5 places A can go, then 4 left B can go, then 3 left C can go, and so on, until we get 5! = 120 possible permutations of ABCDE. If you replace the B with another A to get AACDE now there are only 60 permutations, because half of the original 120 only differed by where the A and the B were relative to one another. By that same logic, AACCE has only 30 combinations, and AACCC has only 10 (seeing why it's 10 and not 20 is actually the trickiest part imo, it's because there are 3! ways to arrange CDE, but only 1 to arrange CCC). AACCC is isomorphic to RRDDD, which is how we get 10 possible paths to solve the 2*3 grid. We can check this with the binomial theorem: ((2+3) choose 3) = 10. What's nice about this step by step approach is that it generalizes not just to non-square grids, but to multiple dimensions as well! Imagine trying to get from the top of a 3 by 3 by 3 Rubik's cube to the bottom, how do you do that? Well how many ways are there to rewrite AAABBBCCC ? The logic above would suggest 9! / (3! 3! 3!) = 1,680 unique paths. And you can just derive it by starting from the degenerate case and figuring out how to slice things up!

soseng 3mo ago

This is also me. I was a double CS and Math major in university and one of my favorite classes as a young lad was combinatorics and probability.. 25 years ago.. It's true, if you don't activate this area of your brain often, it's easier to brute force the solution and reach for the easy mechanical calculation. I can feel this when I'm refactoring code. Today, I just have Claude do it for me with a few instructions. Each day, I feel a tiny bit more ignorant about the actual framework's APIs, its abstractions, and its rules. But I still would rather do other things with my time. As for the problem, luckily for me, this one was easy to derive if you remember factorials, permutations, and remember to account for duplicate patterns

bmenrigh 3mo ago

The 2n choose n solution isn't at all intuitive to me but thinking about it in terms of 40 steps, 20 of them rightward and 20 of them downward an then looking at all distinct permutations of these 40 steps as (40!) / ((20!)^2) is intuitive to me. Then it becomes obvious that since 20 is half of 40, k and n - k are the same number (20), which coincides with the binomial coefficient n! / k!(n - k)!. But this seems like a lucky coincidence in 2 dimensions and if you extended the problem into 3D you'd do better thinking about permutations.

emil-lp 3mo ago
2n choose n is just: you must move East 20 times and South 20 times. Hence any solution looks like a permutation of 20 Es and 20 Ss. Now, only look at the indices for the Es. There are 20 of them. Out of 40. 40 indices, pick 20. Those are East moves, the rest are South moves.
- grumbelbart2 3mo ago
  This interpretation also generalizes nicely to 3d. You have 60 moves, 20 of which will be up (60 choose 20), then 20 are east (40 choose 20), then 20 are south (20 choose 20).
  - C-x_C-f 3mo ago
    That's a nice way to put it. FWIW the generalization of binomial coefficient which allows you to express an n-dimensional solution is called a multinomial coefficient [0]. So in a 3d 20x20x20 box we would have (60 multichoose 20, 20, 20) paths. Also, the wiki article doesn't mention this but the growth rate of (n multichoose k1, k2, ..., km) as we increase n but fix the ratios p1 = k1 / n, ..., pm = km / n is precisely the Shannon entropy of the categorical distribution with probabilities p1, ..., pm . The wiki article for entropy [1] states the result for the binomial coefficient, which can be written as (n choose k) = (n multichoose k, (n - k)) . Actually a lot of basic information-theoretic results about entropy and related quantities (e.g. the properties of the Boltzmann distribution/softmax function) can be derived from similar discrete counting problems after taking a large-n limit. I don't have links at the ready but I might edit this comment if I remember places which explain this stuff. [0] https://en.wikipedia.org/wiki/Multinomial_theorem#Number_of_unique_permutations_of_words https://en.wikipedia.org/wiki/Multinomial_theorem#Number_of_... [1] https://en.wikipedia.org/wiki/Entropy_(information_theory)#Approximation_to_binomial_coefficient https://en.wikipedia.org/wiki/Entropy_(information_theory)#A...

meindnoch 3mo ago

Manhattan distance is 2n steps. Of these, exactly n are to the right, the rest is downwards. A 2n step path is completely determined by choosing which n steps will be to the right. Hence 2n choose n. This is high school math.

Imustaskforhelp 3mo ago

I am currently just going to college after high school and I was preparing for the JEE exam and I remember such a question was within the textbooks of maths itself. At first glance of the question, I had imagined it to be hard but then I read through the solution and other comments to recognize that I had in fact done such a question previously and I had solved it independently during the class if I remember correctly or such classes of problems. I also agree with the AI and spreadsheets part of thing for what its worth but I can only tell more when I get into job but I have heard such things from my senior brothers. I feel like there has to be a right balance of complexity though, and for what its worth I think that there are so many other things that one optimizes later on in life with tangential benefits as well with real knowledge about real life use-cases and edge-cases and so much more! I feel like it would be hard to replace with AI as much as (some) people (mostly Marketing) want it to feel so. I do hope that people don't atrophy their skills though and to solve some coding questions or make projects perhaps as well without LLM by hand if given/having the time. Not everything probably has to be done by the fastest or the most accelerated way as you wouldn't know the destination as it would be found along the way itself. I suppose just like life, so stay safe and have a nice day.

blmarket 3mo ago

I think it's due to calibration - practical work related problems are never that simple & easy so naturally people might start from DP formula. D[A,B] := number of ways to navigate from grid sized AxB = D[A-1,B]+D[A,B-1] and the aha moment is realising this is just a binomial coefficient.

vatsachak 3mo ago

This is why you still work on open source and do coursework for fun. The same reason you go for a jog

shshsjsj 3mo ago

this is like the most basic leetcode question. Some comments here sound like they need to brush up the basics

utopcell 3mo ago
thanks for keeping us honest. what would we ever do without this insightful comment of yours?

Sharlin 3mo ago

If you want to keep your math brain working, and to find use for any and all the math you learned in school, look no further than graphics programming.

jldugger 3mo ago

Project Euler is like this a lot -- it's presented as a coding challenge but half the problems can be optimized to return 5 # because math

Jtsummers 3mo ago
At least the site itself is honest about it, describing the challenges as "mathematical/computer programming problems". I always found it weird when people recommended them as ways to learn a new programming language because, perhaps because of my own math background, I ended up solving most of them with math and so little programming. Where the programs only used the basics of any language so that nothing novel would be learned by rewriting except for how loops look in two different languages (or don't, in the case of some FP languages), or how arrays look, etc.

totetsu 3mo ago

I have to say the youtube algorhythm has done wonders from my mathmatical ability by directing me to so much numberphile and 3Blue1Brown etc. And rapid AI prototyping of ideas involving complex maths has really helped me build and check intuitions about things that i might never have made if I got stuck in the weeds of trying to understand it all from 0. Like oh if this works in 2 dimensions I wonder how it looks in 4. 4d connect 4 is quite a fun game.

SilverSlash 3mo ago

I can definitely relate. My brain also wants to take the path of least effort now, even for simple things like adding two numbers which I could do very quickly in my head in my college days. And with AI the path of least (initial) effort seems to be to just ask the model to solve it. It might get it wrong and then I'll prompt it again and again. But each individual prompt is fairly low effort on my part. Whereas coming up with the right solution myself might've taken less time but the initial effort is a lot more. Last year I used to romanticize about building at least 1 thing each month completely by hand without any LLM coding help. The last such project I worked on was 6 months ago so sadly it's not going so well.

markus_zhang 3mo ago

I could be wrong but I feel this solution is not proved to be correct, but could be nevertheless the answer. On the other side, my Math ability definitely goes down to Calculus and I definitely forgot most about geometry.

noosphr 3mo ago

All problems in project Euler have closed form solutions. The computer programming part of it is just a quick way to develop candidate solutions.

iwsk 3mo ago
https://projecteuler.net/problem=76 https://projecteuler.net/problem=76 does this have a closed form solution? vast majority of the problems don't seem to have a closed form solution

abetusk 3mo ago

I appreciate where the author is coming from, as we often have much more context because of training that have since atrophied a bit, but in defense of the dynamic programming solution, this generalizes very well. As stated, the choose(2n,n) solution of course works but as soon as you deviate from a square, things can get more complicated. What if it's a rectangle? An arbitrary shape? One with holes? The dynamic programming solution takes all of this in stride (assuming, of course, that the conditions of only going right and down still hold). Pascal's triangle is, after all, a dynamic programming solution. It just so happens that there's a "closed form" solution to their entries. I'm all for clever tricks but I also appreciate much more a solution that generalizes well and gives more insight into a class of problems.

Skeime 3mo ago
The rectangle case is just choose(w+h, h), with w, h being the width and height, respectively. (Or choose(w+h, w), which is the same.) Depending on how well you know binomial coefficients, this can also lead you to the dynamic programming solution. After all, for the rectangle case this is nothing but construction of Pascal's triangle by summing two adjacent numbers in a row to get the number below them. If you recognize this, the solution for paths on grids with holes falls out almost immediately.

dominicrose 3mo ago

Even for a math teacher the math isn't the hard part of the job.

GL26 3mo ago

The way the problem was solved at first hand by just "recognizing the pattern of (2n) choose n" wouldn't satisfy me at all, where's the proof ? Why does it work ? This isn't maths, this is "pattern recognition".

igsomething 3mo ago
Maths IS pattern recognition
- BeetleB 3mo ago
  Followed by a proof via induction.
pillmillipedes 3mo ago
in math it's often the case that you notice the solution first and only afterwards prove to yourself that it works. pattern matching and intuition play a large role in math! this is why I'm not a big fan of "show your work": the "work" is however many years it took to build up my intuition, and often any explanation I could type out for my solution would be a retroactive rationalization. it's still useful, sure -especially for catching your errors, but I place it on the opposite end of the open-fake scale than most people. of course here the proof is simple: 20 right moves, 20 down moves, any order => of 40 total moves choose any 20 indices to be your down moves => 40 choose 20 is your answer. would that teach you how to solve the next problem though? I'm not so sure.

a_c 3mo ago

Don't worry, we can regress our programming skill after 6 months of management, management of agents I mean

ramon156 3mo ago

> this is just me fantasizing. At work I would just give it to an AI and continue with my day I'm sure ~4 yrs ago i would have loved the thought of this. It's so boring. My job is so, so boring.

deleted 3mo ago

[deleted]

storus 3mo ago

I noticed the same with me after a few years working; my solution was to take all hard mathy online MS degrees/grad certs available one after the another. Now I can understand how does the generative AI math work while designing an electric motor for my own robot. Though the latest AI can do it all better than me.

jadar 3mo ago

Yeah, this is relatable. Part of it comes down to "use it or lose it." We atrophy when we don't exercise. But at the same time, it might come back to the OP faster than he thinks if he went into it. Also, I've found that with AI I'm able to ask specific questions where I'm hazy and pick things up faster than if I just had to watch hours of lectures to pick something up. (There's a place for both.)

erdaniels 3mo ago

Since I'm between jobs, I've been taking the time to relearn geometry, trig, calc, and linear algebra. I've finished the first two and it's both humiliating and really fun to relearn some math. As an adult, I feel a very different appreciation for how much fundamental math we take for granted. I definitely recommend https://www.khanacademy.org/ https://www.khanacademy.org/ and pauls notes (https://tutorial.math.lamar.edu/ https://tutorial.math.lamar.edu/).

jerf 3mo ago

Something I haven't seen anyone else mention is that this is problem 15. The author probably did the previous 14 problems too. IIRC the problems aren't strictly cumulative but you do generally end up warmed up and with hints about how to approach problem N efficiently from problems [1, N-1]. Skills do decay, I can't deny that. But even when I was still in school going back and doing an end-of-year problem for a class I took two years ago would have been harder than it was for me at the time... but it would have been easier than the first time if I warmed up properly with a bit of review and practice first, and I mean, not just three minutes glancing over things but taking some serious time for it.

esterna 3mo ago
The sequence numbers of problems on Project Euler only represent the order of publication. They aren't deliberately connected except for a few problems that have one or two follow-ups. Most of the first 100 problems can be solved without any understanding of the problem, should you so desire.

1970-01-01 3mo ago

Because the daily world has much less math in it than we care to admit. You don't need calculus to understand which elevator button needs to be pushed.

gradientsrneat 3mo ago

Professional mathematicians and computer scientists use AI as well. Maybe that's not very reassuring from the standpoint of skills regression in modern adult work culture, but at least it demonstrates that skills and tool usage aren't mutually exclusive.

helpfulfrond 3mo ago

A lot of life is "use it or lose it," due to limited resources I imagine.

Martins000 3mo ago

[dead]

lajarre 3mo ago

i often hear this frustration, been hit by it first-hand and am just recovering my keys to overcoming this frustration: * capture (focus on) the joy of doing math; this doesn't get better the more you know (i'd argue, to the contrary); a child figuring out that 2+2 = 3+1 is as profoundly moved as Tao doing his most advanced ones * be responsible and figure out what parts of the maths journey have lastingly influenced your way of thinking about the world; if you trust math is really beautiful or "it's the language of the universe" or something, then it _must_ have an influence on how you see things; not because of the theorems, but because of the practice; isolate this, nurture it