Mathematica, 82 bytes
Using the pattern of submission from @Jenny_mathy 's answer...
(d=x=1;y=0;f:=(10^x-1)10^y;n:=If[y>0,y--;x++,y=d;d++;x=1];While[Mod[f,#]!=0,n];f)&
Input:
[17]
Output:
9999999999999999
And relative to the argument in comments at @Jenny_mathy's answer with @Phoenix ... RepeatedTiming[]
of application to the input [17]
gives
{0.000518, 9999999999999999}
so half a millisecond. Going to a slightly larger input, [2003]
:
{3.78, 99999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999}
a bit under 4 seconds.
Test table: On the first 30 positive integers, the results are
{9, 90, 9, 900, 90, 90, 999999, 9000, 9, 90, 99, 900, 999999,
9999990, 90, 90000, 9999999999999999, 90, 999999999999999999, 900,
999999, 990, 9999999999999999999999, 9000, 900, 9999990, 999,
99999900, 9999999999999999999999999999, 90}
Explanation:
The only magic here is the custom iterator ("iterator" in the CS sense, not the M'ma sense)
n := If[ y>0 , y-- ; x++ , y=d ; d++ ; x=1]
which acts on the global variables x
, the number of leading "9"s, y
, the number of trailing "0"s, and d
, the total number of digits. We wish to iterate through the number of digits, and, for each choice of number of digits, start with the most "0"s and the least "9"s. Thus the first thing the code does is initialize d
to 1, forcing x
to 1 and y
to 0. The custom iterator checks that the string of "0"s can be shortened. If so, it shortens the string of "0"s by one and increases the string of "1"s by one. If not, it increments the number of digits, sets the number of "0"s to one less than the number of digits, and sets the number of "9"s to 1. (This is actually done in a slightly different order to shave a few characters, since the old value of d
is the desired value of y
.)
3proof of well-definedness? – Destructible Lemon – 2017-07-06T05:48:07.790
Similar to this challenge, but I think requiring the smallest one will lead to different strategies.
– xnor – 2017-07-06T05:50:16.4772
@DestructibleLemon This proof suffices, since the result can be multiplied by 9.
– xnor – 2017-07-06T05:50:59.7501I think more test cases would be good to check that solutions require the 9's to come before the 0's. – xnor – 2017-07-06T05:55:14.187
seq 0 $1 1000000 | egrep ^9+0*$ | head -1
works but has a hardcoded upper limit. That works for the test cases but is it ok? – Jerry Jeremiah – 2017-07-06T06:07:49.7771@xnor is
0009999
a number? – Leaky Nun – 2017-07-06T06:26:39.8632@LeakyNun maybe not, but 9900099 is, and shouldn't be allowed according to rules. – DrQuarius – 2017-07-06T06:45:26.007
Nice one. To define it in a better way, i think you should include a realistic range for the input number (ex. 1 to 30 or up to 16 as in your testcases). If you check, most brute force answers given cannot compute N=31, due to timeout error – koita_pisw_sou – 2017-07-06T08:35:38.627
2@koita_pisw_sou the rule is that the program should "theoretically" work for any integer given arbitrary precision and memory and time. – Leaky Nun – 2017-07-06T13:02:04.877