5 ms·
Squared Digit Sum
- nayuki 9y agoThis topic happens to be Project Euler problem #92. https://projecteuler.net/problem=92 https://projecteuler.net/problem=92
- arconis987 9y agoA similar problem was in Google Code Jam 2009 :) https://code.google.com/codejam/contest/188266/dashboard https://code.google.com/codejam/contest/188266/dashboard
- labster 9y agoYou can compete against other code golfers for the shortest Happy Numbers solution on code-golf.io https://code-golf.io/happy-numbers https://code-golf.io/happy-numbers
- jwilk 9y agoSketch of a proof: Let f(n) be the sum the squares of digits of n. For k-digit number: f(n) ≤ 81k. That is: f(n) ≤ 81 × (1 + ⌊log₁₀n⌋) It's pretty clear that if n≥1000, f(n) < n. So the n, f(n), f(f(n)), ... sequence will eventually reach a number below 1000. Mechanical proof for numbers below 1000 is in the article.
- mannykannot 9y agoGood point. The first response to the original article mentions 162 (2 * 81) as a value that the process will always eventually fall below, presumably arrived at by this argument.
- resource0x 9y ago> if n≥1000, f(n) < n And this is what makes the setup not very interesting. Compare with 3x+1 problem, where the sequence can grow, but eventually comes down (there's a simple probabilistic argument for that, but no formal proof).
- Someone 9y agoBecause f(n) = log(n) eventually grows arbitrarily slower then f(n) = n, no matter what the base of that logarithm is, you can generalize that to arbitrary number base b > 2 and arbitrary powers p > 2, and show that any starting number will eventually reach a cycle. Now, one can ask question such as: - for which (number base, power) pairs is that cycle unique? - for which (number base, power) pairs is that cycle shortest? (For example, 153 = 1³ + 5³ + 3³, so if (base 10, power 3) has only one such cycle, it has length 1. Similarly, 4150 = 4^⁵ + 1^⁵ + 5^⁵ + 0^⁵ could be the unique cycle of length 1 for base 10, power 5. - what does the function f(base, power) look like?
- theophrastus 9y agoThese are certainly cool. Yet everytime I've stumbled over them, I find that "Integer Sequences"[1] 'already did it'. And that's true for this case too[2]. [1] https://oeis.org/ https://oeis.org/ [2] https://oeis.org/A000216 https://oeis.org/A000216
- jwilk 9y agoOEIS links to PDF with Arthur Porges's proof: https://oeis.org/A003621/a003621.pdf https://oeis.org/A003621/a003621.pdf
- taeric 9y agoLove the plug for emacs org mode. There are few things I evangelize. Sadly, none of my efforts have gotten anyone using it, to my knowledge. :/
- eat_veggies 9y agoI've heard a lot of people talk about how it's a real game changer and that they can't live without it, but I'm not really clear on the specifics as to why. Are there any "killer features" of org mode that I should know about? What exactly does it replace or augment in your workflow? You might be about to get yourself your first conversion to this tool!
- taeric 9y agoThe article that was posted a few days about about literate dev ops covered all of the amazing features, to me. The part that is hard to really convey is just the fun of it. Being able to run a log dive to grab some data using standard grep/whatever, then to immediately pull it into either R or Python or just Gnuplot to get a visual is quite a nice trick. Top it off with a quick export to pdf/html/markdown to send to someone to confirm it. (Typically a stakeholder.) Add to this emacs TRAMP capabilities and I just need whatever tool I want on a machine I can ssh to. Don't have a good install of python locally for some reason, just set the :dir attribute of the block to my machine (or docker container. Or a series of jumps through combinations!) that has it, and I'm good. It does have some growing pains sometimes. I found that the SQL plugin didn't do the passwords as I wanted it to. But, that was a simple breakpoint and hot code fix away. (I, regretably, did not prepare a patch to send upstream...)
- eat_veggies 9y agoThat sounds dope. I'll give it a spin! It'll be my first time using emacs--do you recommend plain emacs, or something like spacemacs?
- taeric 9y ago
- early 9y agoI am happy to see that 42 is part of the answer
- Goopplesoft 9y agohttps://en.wikipedia.org/wiki/Happy_number https://en.wikipedia.org/wiki/Happy_number
- gweinberg 9y agoHappy numbers led me to Fortunate numbers, which are Fortunate not because they are well off but because the guy studying them was named Fortune. https://en.wikipedia.org/wiki/Fortunate_number https://en.wikipedia.org/wiki/Fortunate_number Fortune conjectured that all Fortunate numbers are prime. I know jack about number theory but isn't that obvious from the density of primes? If there were a composite Fortunate number Fn it couldn't have any factors less than the nth prime number, which means it would have to be greater than the nth prime number squared.
- cperciva 9y agoNot at all obvious. It is a very open question whether prime gaps are bounded by ~(log N)^2... AFAIK, even assuming the GRH, the best upper bound is roughly N^(1/2).