Timeline for Find a multiple of a given number whose decimal representation looks like binary
Current License: CC BY-SA 3.0
76 events
| when toggle format | what | by | license | comment | |
|---|---|---|---|---|---|
| Aug 28, 2023 at 1:12 | answer | added | Julian | timeline score: 1 | |
| Aug 11, 2023 at 10:31 | answer | added | lyxal♦ | timeline score: 1 | |
| Aug 10, 2023 at 14:37 | answer | added | Jordan | timeline score: 0 | |
| Aug 10, 2023 at 14:25 | answer | added | The Empty String Photographer | timeline score: 1 | |
| Aug 10, 2023 at 14:02 | answer | added | Ashlin Harris | timeline score: 2 | |
| Aug 10, 2023 at 12:42 | answer | added | The Thonnu | timeline score: 1 | |
| Jul 15, 2021 at 9:31 | answer | added | emanresu A | timeline score: 1 | |
| Nov 5, 2020 at 20:21 | answer | added | Dominic van Essen | timeline score: 0 | |
| Nov 5, 2020 at 19:38 | answer | added | caird coinheringaahing♦ | timeline score: 1 | |
| Mar 1, 2020 at 17:55 | vote | accept | anatolyg | ||
| Sep 22, 2017 at 22:04 | comment | added | Stan Strum | @SuperJedi224 multiples of mine that fit this answer will be at minimum 111111111, because any number x where x % 9 = 0, the numbers added up recursively will equal 9 | |
| Sep 22, 2017 at 21:44 | answer | added | phroureo | timeline score: 2 | |
| Sep 5, 2017 at 10:24 | answer | added | Shaggy | timeline score: 0 | |
| Sep 5, 2017 at 9:53 | answer | added | Mr. Xcoder | timeline score: 1 | |
| Apr 13, 2017 at 12:41 | history | edited | CommunityBot | replaced http://codereview.stackexchange.com/ with https://codereview.stackexchange.com/ | |
| Oct 24, 2016 at 20:02 | history | edited | mbomb007 | CC BY-SA 3.0 | added 59 characters in body |
| Nov 4, 2015 at 10:51 | comment | added | anatolyg | @Candles If you can prove that the worst case is repeated 9's (empirically correct up to quite a few repeated 9's), there's your constructive proof. | |
| Nov 4, 2015 at 8:15 | comment | added | Candles | I'm like 95% certain that the length of the output is linear in the length of the input; I'm trying to find an existence proof and possibly a constructive proof if I can get that far. | |
| Oct 28, 2015 at 10:55 | vote | accept | anatolyg | ||
| Mar 1, 2020 at 17:55 | |||||
| Oct 28, 2015 at 9:54 | comment | added | primo | The Bounty was awarded to aditsu's c answer. Final scoreboard: codepad.org/DVRGITHP (average of 5 runs). I didn't test any "count by one" solutions, so if I've missed yours, and it's faster than aditsu's c, I'll double down on the bounty. | |
| S Oct 28, 2015 at 9:45 | history | bounty ended | primo | ||
| S Oct 28, 2015 at 9:45 | history | notice removed | primo | ||
| Oct 28, 2015 at 8:27 | comment | added | Candles | I've a proof that the length of the output is indeed at most linear in the size of the input (and thus exponential in the length of the input), but it cannot fit in a comment box. It relies on two ideas: 1) That for any N, 10^i % N has a period with length <= N - 1 or has finite support, and 2) There exists a multiple of N that equals a linear combination of numbers less than N such that their coefficients sum to at most N. | |
| Oct 27, 2015 at 11:23 | comment | added | primo | @PeterTaylor if it produces the correct output for all values between 1-10000, I will consider it valid. I will be evaluating all solutions shortly. | |
| Oct 27, 2015 at 8:45 | answer | added | Joba | timeline score: 3 | |
| Oct 27, 2015 at 7:24 | answer | added | aditsu quit because SE is EVIL | timeline score: 2 | |
| Oct 26, 2015 at 23:38 | answer | added | Peter Taylor | timeline score: 2 | |
| Oct 26, 2015 at 13:40 | comment | added | Peter Taylor | @primo, how special-cased can the fast code be? E.g. can it restrict to using narrower int types which wouldn't be sufficient for input 99999999? | |
| Oct 23, 2015 at 9:15 | answer | added | mroman | timeline score: 0 | |
| Oct 21, 2015 at 13:58 | answer | added | Anders Kaseorg | timeline score: 4 | |
| Oct 20, 2015 at 16:46 | answer | added | edc65 | timeline score: 2 | |
| Oct 20, 2015 at 16:21 | comment | added | primo | @edc65 Output must be generated, although for timing it will be discarded (i.e. piped to /dev/null. I will however check it for accuracy). You may optimize your solution to produce each value sequentially, if that helps. If you prefer to be timed with a specific interpreter/compiler, please specify. | |
| Oct 20, 2015 at 16:15 | comment | added | edc65 | @primo re bounty: time to calc or time to print in console? Maybe redirect to file | |
| S Oct 20, 2015 at 12:02 | history | bounty started | primo | ||
| S Oct 20, 2015 at 12:02 | history | notice added | primo | Reward existing answer | |
| Oct 19, 2015 at 21:44 | answer | added | cpt_peter | timeline score: 0 | |
| Oct 19, 2015 at 16:56 | answer | added | Joe | timeline score: 0 | |
| Oct 19, 2015 at 15:03 | answer | added | Adám | timeline score: 1 | |
| Oct 19, 2015 at 11:14 | answer | added | G. Sliepen | timeline score: 2 | |
| S Oct 18, 2015 at 23:54 | history | suggested | Mama Fun Roll | CC BY-SA 3.0 | 1) It has already been proven that y exists for every x. 2) y should be greater than 0 to prevent any loophole stuff. |
| Oct 18, 2015 at 23:29 | review | Suggested edits | |||
| S Oct 18, 2015 at 23:54 | |||||
| Oct 18, 2015 at 11:31 | answer | added | Cabbie407 | timeline score: 1 | |
| Oct 17, 2015 at 15:28 | answer | added | Rnet | timeline score: 5 | |
| Oct 17, 2015 at 10:51 | answer | added | wastl | timeline score: 1 | |
| Oct 17, 2015 at 7:59 | history | tweeted | twitter.com/StackCodeGolf/status/655292064503042048 | ||
| Oct 17, 2015 at 1:50 | answer | added | edc65 | timeline score: 6 | |
| Oct 16, 2015 at 16:29 | comment | added | aditsu quit because SE is EVIL | @anatolyg mine is not brute force | |
| Oct 16, 2015 at 16:21 | answer | added | Peter Lenkefi | timeline score: 1 | |
| Oct 16, 2015 at 16:08 | comment | added | Addison Crump | Umm... there is always a value that can be resolved that looks like binary (circumventing the output 0 rule), simply because there is an infinite range of numbers. | |
| Oct 16, 2015 at 15:59 | answer | added | Addison Crump | timeline score: 2 | |
| Oct 16, 2015 at 15:51 | comment | added | anatolyg | I guess I was too optimistic about complexity, and it's impossible to make it polynomial on the size of input - the size of the output seems to be exponential on input. But hey - all the 16 answers so far are brute-force?! Surely you can do better! | |
| Oct 16, 2015 at 15:10 | answer | added | insertusernamehere | timeline score: 4 | |
| Oct 16, 2015 at 14:26 | answer | added | aditsu quit because SE is EVIL | timeline score: 20 | |
| Oct 16, 2015 at 13:38 | comment | added | aditsu quit because SE is EVIL | @SuperJedi224 well, you need at least 9 1's to get a multiple of 9 | |
| Oct 16, 2015 at 13:19 | answer | added | raznagul | timeline score: 0 | |
| Oct 16, 2015 at 12:32 | comment | added | jazzpi | input();print 0 - you should probably limit y to > 0 ;) | |
| Oct 16, 2015 at 8:07 | answer | added | plannapus | timeline score: 3 | |
| Oct 16, 2015 at 7:19 | comment | added | anatolyg | @RetoKoradi Polynomial in the number of digits, of course! Otherwise, you cannot run it => no fun. | |
| Oct 16, 2015 at 6:51 | answer | added | izzyg | timeline score: 8 | |
| Oct 16, 2015 at 5:49 | answer | added | primo | timeline score: 11 | |
| Oct 16, 2015 at 4:19 | answer | added | xnor | timeline score: 4 | |
| Oct 16, 2015 at 4:01 | answer | added | xnor | timeline score: 12 | |
| Oct 16, 2015 at 3:56 | answer | added | Reto Koradi | timeline score: 4 | |
| Oct 16, 2015 at 3:48 | comment | added | Reto Koradi | By polynomial complexity, do you mean polynomial in the number of digits of the input, or polynomial in the value of the input? | |
| Oct 16, 2015 at 3:15 | answer | added | Mama Fun Roll | timeline score: 12 | |
| Oct 16, 2015 at 3:12 | answer | added | Maltysen | timeline score: 2 | |
| Oct 16, 2015 at 2:42 | comment | added | Sp3000 | Related Project Euler problem, for anyone else who thought this question looked familiar | |
| Oct 16, 2015 at 2:02 | comment | added | SuperJedi224 | Multiples of 9 seem to produce unusually high results. | |
| Oct 16, 2015 at 0:27 | answer | added | user45726 | timeline score: 5 | |
| Oct 15, 2015 at 22:49 | answer | added | SuperJedi224 | timeline score: 4 | |
| Oct 15, 2015 at 22:09 | answer | added | nimi | timeline score: 9 | |
| Oct 15, 2015 at 22:09 | answer | added | Celeo | timeline score: 6 | |
| Oct 15, 2015 at 22:01 | answer | added | DavidC | timeline score: 3 | |
| Oct 15, 2015 at 21:57 | comment | added | feersum | It should always be solvable. Clearly there must exist at least one q such that there are an infinite number of n such that 10^n mod x = q. Take x such values of n and add together the respective powers 10^n. | |
| Oct 15, 2015 at 21:49 | history | edited | anatolyg | CC BY-SA 3.0 | made spec consistent with examples |
| Oct 15, 2015 at 21:39 | history | asked | anatolyg | CC BY-SA 3.0 |