14
1
Inspired by this CMC
Given a positive integer greater than 0, perform the following operation on it:
- If all ten single digits (
1234567890
) are in the number at least once, output the count and exit the program - Otherwise, double the number and repeat, incrementing the count.
The count starts at 0 and is the number of times the input was doubled. For example, if the input were 617283945, it would need to be doubled once because 1234567890 has all 10 digits in it.
This is a code-golf so shortest code wins. Input may be taken as a string, if you want.
Test cases
input => output
617283945 => 1
2 => 67
66833 => 44
1234567890 => 0
100 => 51
42 => 55
Can we take input as a string? – Stephen – 2017-09-14T19:18:30.977
@Stephen you may take input as a string. – caird coinheringaahing – 2017-09-14T19:19:15.637
@Shaggy what do you think they should be? Also, its
66833
with 23
s – caird coinheringaahing – 2017-09-14T20:25:03.587@Shaggy It might be that test case 2 will need a big integer since doubling 2 67 times gives 2^68 – miles – 2017-09-14T20:27:24.533
@Shaggy as with all challenges, no. – caird coinheringaahing – 2017-09-14T20:31:06.340
3Is it guaranteed that for any
n
there exists somek
such thatnk
is pandigital? I'd love to see a proof. – shooqie – 2017-09-14T20:57:27.583@shooqie That question was asked in the Maths chat room, but wasn't answered. I think that every
n
greater than 0 can be doubled into pandigitality. (Is that the right word?) – caird coinheringaahing – 2017-09-14T20:59:11.043I checked all inputs up to 100,000 and the largest value for
– Engineer Toast – 2017-09-15T13:19:59.743n
was 78 given an input of1471
. There may be a largern
for long numbers but my stupid VBA solution takes about 8 seconds per 1,000 inputs and I don't want to wait that long. I did find an interesting pattern, though. For the first 100,000 inputs, the number of times a certainn
occurred fits a normal distribution.What does "CMC" mean? – bfontaine – 2017-09-15T20:04:08.560
1@bfontaine Chat Mini Challenge – caird coinheringaahing – 2017-09-15T20:04:29.827
3@shooqie Proof! For any n which is coprime to 10, it's also coprime to 10^10, and so there exists some k such that nk is 1 mod 10^10. Then 1234567890*nk = 1234567890 mod 10^10, so each digit necessarily appears at least once. If not, multiply by 2, 5, or 25 as necessary to make the last non-zero digit coprime with 10, and a variant of the above proof works (formally, n = 10^m * p, where p satisfies the above condition, then 1234567890*p*k as above is pandigital, so 1234567890*p*k10^m = 1234567890k*n is). :) – B. Mehta – 2017-09-17T01:43:47.090
A similar idea of modular inverses proves this nicely if the question asked about tripling instead, doubling only seems a little harder. – B. Mehta – 2017-09-17T01:53:49.780
@EngineerToast 1471 stays the largest up to 1 000 000, and is in fact the last value for which the output reaches 78 below a million. – B. Mehta – 2017-09-17T02:33:32.927
@B.Mehta Both are true up to at least
160 868 750
, too. – Engineer Toast – 2017-10-12T21:24:30.360There's no result higher than 78 in the first 1,000,000,000 values - is there a mathematician who can tell us whether any larger results can be proved or disproved? – Toby Speight – 2017-11-21T09:10:19.350