6 ms·
A happy numeric coincidence
- sonofgod 8y agoI'm getting bigger numbers from a very quick script -- am I missing something? digitalsum(999^75) = 999 999^75 = 927708673390001466432161699937587612771693772928727827334425528520027513591277141564708297244305734237029149442895264407211992619276548532187236223108524403378301874096420069132958960388059297398105903507708174617522225074999
- sonofgod 8y agodef test(x, y, debug=True): num = x**y digitalsum = sum(int(a) for a in str(num)) if x == digitalsum and debug: print x, y, num return x == digitalsum for i in range(1,1000): for j in range(1,100): if test(i, j): print i, j
- lmcarreiro 8y agoAfter you calc X^Y, when you will calc X^(Y+1), doesn't it worth to calc using the previous result (X^Y)*X instead of another power X^(Y+1) ?
- deleted 8y ago[deleted]
- kazinator 8y agoYou will find here that the run-time is swamped by the digit breakdown and summing, so that exponentiation versus accumulated product doesn't make a palpable difference.
- kazinator 8y agoTXR lisp: This is the TXR Lisp interactive listener of TXR 203. Quit with :quit or Ctrl-D on empty line. Ctrl-X ? for cheatsheet. 1> (each ((x (range 2 1000))) ;; 1 is uninteresting (each ((y (range 1 100))) (let ((z (expt x y))) (when (= x (sum (digits z))) (put-line `@x @y`))))) 2 1 3 1 4 1 5 1 [...] 963 69 964 75 964 78 991 71 999 75
- kazinator 8y agoUsing successive multiplication instead of exponent operation: 6> (each ((x (range 2 1000))) (each ((y (range 1 100)) ;; needed just for the put-line (z [giterate true (op * x) x])) (when (= x (sum (digits z))) (put-line `@x @y`)))) (Makes no difference; run time is vastly dominated by the contribution of the (sum (digits z)) business.)
- lmcarreiro 8y ago@pavel_lishin what algorithm did you use to find these results?
- pavel_lishin 8y agoSorry, I'm not the author of the post!
- deleted 8y ago[deleted]
- hinkley 8y agoAll multiples of 9 have digits that add up to 9. This is something kids learn. Why does it work? 9 is 10 - 1, so every time you add another nine the tens digit goes up by one and the ones digit down by one, maintaining the sum of digits. Similar thing happens at three digits, four digits, etc, because 9 < 10, no digit other than the ones digit ever goes up by more than 1, and a 9 becomes a 0 when you carry a one. That this pattern didn’t swamp the results makes me wonder what kind of bug the author has in the scanning code. [edit: seems I forgot about situations like 9 x 11 x N, where the digits can add up to 18, 27, etc due to all the 8 and 9 digits, so the algorithm will only find multiples of 9 with lots of small digits in it.]
- midgetjones 8y agoBut not all of the numbers are multiples of 9
- AGoodName 8y agoThe digits add to 0 in mod 9 and he's looking for precisely 9. eg. the sum of digits for 9^3 = 18. That's why you don't see 9's everywhere.
- gweinberg 8y agoSomething lie that happens in all bases e.g. in base 8 all multiples of 7 add up to 7 (if you keep adding), in hex all multiples of f add up to f, and in binary everything eventually adds up to 1 (except zero). Similarly, in base 8 7^2 is 61 and in hex f^2 is e1. (n-1)^2 = n^2 - 2*n + 1 = n(n-2) + 1 which in base n is written with n-2 as the fist digit and 1 as the second digit.
- white-flame 8y agoThe omission is that it's simply recursive. You might add the digits up to 36, whose digits then add up to 9. Simply reapply to the sum if the sum has more than 1 digit, and you'll still arrive at 9.
- Aardwolf 8y agoNeat, but why is for example 163^16 such a coincidence? It's not that unlikely for digits to add up to 163, and given that you can choose both a base and an exponent, there's bound to be many that work out like this. 163^16 has 36 digits, so expected sum (average expected value of a random digit 0-9 being 4.5) be 162. So that's even pretty close to 163. Also, why limit this to base 10? Anything with base 10 digits is not the purest possible math imho because it depends on the arbitrary value 10 while you could generalize to any other value.
- Aardwolf 8y agoYou can speed up brute force search by starting somewhere before where log10(x^y) * 4.5 is roughly equal to x. For example 2222^140 is 2110 which is close to 2222. Then brute force search from there and you get: 2222 ^ 145
- klodolph 8y agoHow much does this speed up brute force search, though? You have to actually compute the exponent and digit sums. If I iterate over the powers of N from N^I to N^J, I do something like O((J-I)^2*log N) work doing multiplications the naive way.
- sephoric 8y agoI think one reason to limit to base 10 is because we don't have an arbitrary number of digits, we only have maybe 36 if we use the full alphabet. And it will be difficult for people to follow along with if it's something they aren't used to calculating in. But I'm also guessing the results will become a lot less "rare" which is part of the cool factor here.
- rdwampler 8y agoThese are called "Reacher numbers." http://recursed.blogspot.com/2007/09/mathematics-in-jack-reacher-novel.html http://recursed.blogspot.com/2007/09/mathematics-in-jack-rea... Base 10: https://oeis.org/A023106 https://oeis.org/A023106 Base 2: https://oeis.org/A256590 https://oeis.org/A256590
- deleted 8y ago[deleted]
- Someone 8y agoAlso: http://oeis.org/A152147 http://oeis.org/A152147 “Irregular triangle in which row n lists k > 0 such that the sum of digits of k^n equals k.”.
- pavel_lishin 8y agoThat was a pretty great post, if only for this line: > Extra credit: explain why nobody cares.
- proflos 8y agohttps://oeis.org/A023106 https://oeis.org/A023106
- klodolph 8y agoJust curious how fast brute force search is. Found some larger numbers like 7793^451. Computing the exponents in base 10 seems to be a fairly fast way of doing things, since this is not very hard and radix conversion is a comparatively slow operation.
- RickJWagner 8y agoHacker News paydirt! Nerdy enough (and well written enough) that I'll add this blog to my RSS reader. 2019 is off to a good start!