20
\$\begingroup\$

A number of programming languages construct large integers through 'concatenating' the digit to the end of the existing number. For example, Labyrinth, or Adapt. By concatenating the digit to the end, I mean that, if the existing number is \$45\$, and the digit is \$7\$, the result number is \$457\:(45 \times 10 + 7)\$.

A constructed number is a number that can be built this way through the use of the multiples of single digit numbers: \$1, 2, 3, 4, 5, 6, 7, 8, 9\$ A.K.A an element in one of these 9 sequences:

$$1, 12, 123, 1234, 12345, \: \dots$$ $$2, 24, 246, 2468, 24690, \: \dots$$ $$3, 36, 369, 3702, 37035, \: \dots$$ $$4, 48, 492, 4936, 49380, \: \dots$$ $$5, 60, 615, 6170, 61725, \: \dots$$ $$6, 72, 738, 7404, 74070, \: \dots$$ $$7, 84, 861, 8638, 86415, \: \dots$$ $$8, 96, 984, 9872, 98760, \: \dots$$ $$9, 108, 1107, 11106, 111105, \: \dots$$

To provide an example of how the sequences are constructed, here's how the sequence for \$a = 3\$ in constructed:

$$\begin{align} u_1 = && a = && 3 & = 3\\ u_2 = && 10 \times u_1 + 2 \times a = && 30 + 6 & = 36 \\ u_3 = && 10 \times u_2 + 3 \times a = && 360 + 9 & = 369 \\ u_4 = && 10 \times u_3 + 4 \times a = && 3690 + 12 & = 3702 \\ u_5 = && 10 \times u_4 + 5 \times a = && 37020 + 15 & = 37035 \\ u_6 = && 10 \times u_5 + 6 \times a = && 370350 + 18 & = 370368 \\ \end{align}$$ $$\vdots$$ $$\begin{align} u_{33} = && 10 \times u_{32} + 33 \times a = && 37\dots260 + 99 & = 37\dots359 \\ u_{34} = && 10 \times u_{33} + 34 \times a = && 37\dots359 + 102 & = 37\dots3692 \end{align}$$ $$\vdots$$

\$u_{33}\$ and \$u_{34}\$ included to demonstrate when \$n \times a \ge 100\$. A lot of digits dotted out for space.

It may still not be clear how these sequences are constructed, so here are two different ways to understand them:

  • Each sequence starts from the single digit. The next term is found by taking the next multiple of that digit, multiplying the previous term by \$10\$ and adding the multiple. In sequence terms:

    $$u_n = 10 \times u_{n-1} + n \times a, \: \: u_1 = a$$

    where \$a\$ is a single digit (\$1\$ through \$9\$)


  • Each of the \$9\$ elements at any point in the sequence (take \$n = 3\$ for instance) are the multiples of \$123\dots\$ from \$1\$ to \$9\$, where \$123\dots\$ is constructed by \$u_{n+1} = 10 \times u_n + n\$ \$(1, 12, 123, \dots, 123456789, 1234567900, 12345679011, \dots)\$

    So the first values are \$1 \times 1, 2, 3, \dots, 8, 9\$, the second are \$12 \times 1, 2, 3, \dots, 8, 9\$, the third \$123 \times 1, 2, 3, \dots, 8, 9\$, etc.

Your task is to take a constructed number as input and to output the initial digit used to construct it. You can assume the input will always be a constructed number, and will be greater than \$0\$. It may be a single digit, which maps back to itself.

You may take input in any reasonable manner, including as a list of digits, as a string etc. It is acceptable (though not recommended) to take input in unary, or any other base of your choosing.

This is a so the shortest code wins!

Test cases

       u_n        => a
 37035            => 3
 6172839506165    => 5
 5                => 5
 246913580244     => 2
 987654312        => 8
 61728395061720   => 5
 1111104          => 9
 11111103         => 9
 111111102        => 9
 2469134          => 2
 98760            => 8
 8641975308641962 => 7

or as two lists:

[37035, 6172839506165, 5, 246913580244, 987654312, 61728395061720, 1111104, 11111103, 111111102, 2469134, 98760, 8641975308641962]
[3, 5, 5, 2, 8, 5, 9, 9, 9, 2, 8, 7]

When I posted this challenge, I didn't realise it could be simplified so much by the method used in Grimmy's answer, and so therefore would be very interested in answers that take a more mathematical approach to solving this, rather than a 'digit' trick (Obviously all valid answers are equally valid, just what I'd be interested in seeing).

\$\endgroup\$
1

18 Answers 18

32
+500
\$\begingroup\$

05AB1E, 7 5 4 bytes

>9*н

Try it online!

>            # input + 1
 9*          # * 9
   н         # take the first digit

The \$(n-1)^{th}\$ term of the sequence starting with \$a\$ is \$\sum _{i=1}^{n-1} a \times i \times 10^{i-1} = a \times \frac{(10^n - 1) / 9 - n}{9}\$. Multiply that by \$9\$ and add \$a\times n\$, and you get \$a \times \frac{10^n - 1}{9}\$, aka the digit \$a\$ repeated \$n\$ times. Turns out adding \$9\$ instead of \$a\times n\$ works for \$n=1\$, and for bigger \$n\$ the linear difference is negligible next to the exponential growth.

\$\endgroup\$
9
  • 6
    \$\begingroup\$ Hmm, that doesn't bode well for this challenge if it can be simplified that easily \$\endgroup\$ Sep 4, 2019 at 14:41
  • 11
    \$\begingroup\$ You have approximately 1 byte of code for 800 bytes of challenge explanation. :p \$\endgroup\$
    – Arnauld
    Sep 4, 2019 at 15:21
  • 8
    \$\begingroup\$ @Joel the (n-1)th term of the sequence starting with a is a * (((10**n - 1) / 9 - n) / 9). Multiply that by 9 and add a*n, and you get a * ((10**n - 1) / 9), aka the digit a repeated n times. Turns out adding 9 instead of a*n works for n=1, and for bigger n the constant difference is negligible next to the exponential growth. \$\endgroup\$
    – Grimmy
    Sep 4, 2019 at 16:43
  • 3
    \$\begingroup\$ @Grimy Thanks a lot for the explanation. Maybe you can put it into your post. \$\endgroup\$
    – Joel
    Sep 4, 2019 at 18:21
  • 4
    \$\begingroup\$ Nominated as promised :) \$\endgroup\$ Mar 20, 2020 at 8:43
3
\$\begingroup\$

Stax, 5 bytes

^9*Eh

Run and debug it

\$\endgroup\$
3
\$\begingroup\$

Charcoal, 7 bytes

§I×⁹⊕N⁰

Try it online! Link is to verbose version of code. @Grimy's method of course. Here's a 27 byte mathematical approach:

NθW¬№Eχ×κ↨υχθ⊞υLυI⌕Eχ×ι↨υχθ

Try it online! Link is to verbose version of code. Crashes on invalid inputs. Explanation:

Nθ

Input the constructed number.

W¬№Eχ×κ↨υχθ

Interpret the list as a number in base 10, multiply by all numbers from 0 to 9, and see whether the constructed number appears.

⊞υLυ

Push the list's length to itself. The list therefore becomes of the form [0, 1, 2, ..., n].

I⌕Eχ×ι↨υχθ

Recreate the constructed numbers but this time find and output the index at which the input number appeared.

\$\endgroup\$
3
\$\begingroup\$

MathGolf, 6 bytes

)9*▒├Þ

Try it online!

Unfortunately, there's no head operation in MathGolf, so I have to make do with ▒├Þ to convert to string, pop from the left and discard all but the top of stack.

\$\endgroup\$
3
\$\begingroup\$

Labyrinth,  28 22  20 bytes

9 10/;!@
? _ :
)*"""

Applies the digit-based method described by Grimy by repeated integer division by ten until zero is found.

Try it online!

\$\endgroup\$
3
\$\begingroup\$

Python 3, 22 bytes

lambda i:str(-~i*9)[0]

Try it online!

Port of Grimy's 05AB1E answer


Python 3, 72 bytes

f=lambda i,j=1,l=1,k=2:l*(i==j)or f(i,*(10*j+k*l,l+1,l,l+1,k+1)[i<j::2])

Try it online!

Explanation

Recursive function. Iterates over the sequence for each digit l, starting at 1. If the input i is equal to the current iteration j, the corresponding digit l is returned. Else, if the current value j in the sequence exceeds the input value i, it will increment the digit l and start over. Argument k is used to increment the multiplication factor.

\$\endgroup\$
2
\$\begingroup\$

Jelly, 5 bytes

‘×9DḢ

Try it online!

Using Grimy's approach.

\$\endgroup\$
2
\$\begingroup\$

Japt -g, 7 6 5 bytes

-1 byte thanks to Shaggy

Takes input as a string

i°U*9

Try it | Test multiple inputs

\$\endgroup\$
1
  • 1
    \$\begingroup\$ 5 bytes, taking input as a string. \$\endgroup\$
    – Shaggy
    Sep 4, 2019 at 19:29
2
\$\begingroup\$

Java 8, 23 bytes

n->(n*9+9+"").charAt(0)

Port of @Grimy's 05AB1E answer, so make sure to upvote him!

Try it online.

But because I kinda feel bad for @cairdCoinheringaahing, here a brute-force approach with a bit more afford (83 bytes):

n->{long r=n,a=0,u,k;for(;++a<10;r=u>n?r:a)for(k=2,u=a;u<n;)u=u*10+k++*a;return r;}

Try it online.

Explanation:

n->{                 // Method with long as both parameter and return-type
  long r=n,          //  Result, starting at the input in case it's already a single digit
       a=0,          //  The digit to start the sequence with
       u,            //  The last number of the sequence we're building for digit a
       k;            //  Multiplier which increments each iteration
  for(;++a<10;       //  Loop in the range [1,9] (over each digit):
      r=u>n?         //    After ever iteration: if `u` is larger than the input:
            r        //     Keep the result the same
           :         //    Else:
            a)       //     Change the result to `a`
    for(k=2,         //   Reset `k` to 2
        u=a;         //   Reset `u` to the current digit `a`
        u<n;)        //   Inner loop as long as `u` is smaller than the input
      u=             //    Change `u` to:
        u*10         //     10 times the current `u`
            +k++*a;  //     With `k` multiplied by `a` added
                     //     (after which `k` increases by 1 with `k++`)
  return r;}         //  And after we iterated over each digit, return the result
\$\endgroup\$
2
\$\begingroup\$

Whitespace, 108 bytes

[S S S N
_Push_0][S N
S _Duplicate_0][T   N
T   T   _Read_STDIN_as_integer][T   T   T   _Retrieve_input][S S S T    N
_Push_1][T  S S S _Add][S S S T S S T   N
_Push_9][T  S S N
_Multiply][S S S T  N
_Push_1][N
S S N
_Create_Label_LOOP][S S S T S T S N
_Push_10][T S S N
_Multiply][S N
S _Duplicate][S T   S S S T S N
_Copy_0-based_2nd]S N
T   Swap_top_two][T S S T   _Subtract][N
T   T   S N
_If_neg_jump_to_Label_PRINT][N
S N
N
_Jump_to_Label_LOOP][N
S S S N
_Create_Label_PRINT][S S S T    S T S N
_Push_10][T S T S _Integer_divide][T    S T S _Integer_divide][T    N
S T _Output_top_as_number]

Letters S (space), T (tab), and N (new-line) added as highlighting only.
[..._some_action] added as explanation only.

Port of @Grimy's 05AB1E answer, except that I don't have a builtin to get the first digit. ;)

Try it online (with raw spaces, tabs and new-lines only).

Explanation in pseudo-code:

Integer i = STDIN as integer
i = i + 1
i = i * 9
Integer t = 1
Start LOOP:
  t = t * 10
  If(i - t < 0):
    Call function PRINT
  Go to next iteration of LOOP

function PRINT:
  t = t / 10
  i = i / t    (NOTE: Whitespace only has integer-division)
  Print i as integer to STDOUT
\$\endgroup\$
1
\$\begingroup\$

JavaScript (ES6),  16  15 bytes

Thanks to @Grimy for lifting the 32-bit constraint I had with the previous version.

Using Grimy's magical incantation. Takes input as a string.

n=>(n*9+9+n)[0]

Try it online!


JavaScript (ES6), 53 bytes

Naive brute force approach.

n=>(g=(k,x=i=0)=>x>n?g(k+1):x<n?g(k,++i*k+10*x):k)(1)

Try it online!

\$\endgroup\$
3
  • \$\begingroup\$ -~n*9 can be n*9+9, which is the same bytecount but should get rid of the 32-bit limitation if I understood correctly. \$\endgroup\$
    – Grimmy
    Sep 4, 2019 at 15:21
  • \$\begingroup\$ the brute force works for a>=10, like 14808 \$\endgroup\$ Sep 4, 2019 at 15:43
  • 1
    \$\begingroup\$ @NahuelFouilleul if we consider a>=10, the answer is no longer unique (14808 could be either the 4th term of a=12, or the first term of a=14808). If outputting any of those is allowed, n=>n works for all inputs. \$\endgroup\$
    – Grimmy
    Sep 4, 2019 at 15:52
1
\$\begingroup\$

PHP, 20 bytes

<?=(_.++$argn*9)[1];

Try it online!

Yet another Grimy's answer port!

\$\endgroup\$
1
\$\begingroup\$

Jelly, 8 bytes

RRḌ÷@fⱮ9

Try it online!

A full program that takes an integer and prints the starter digit. Doesn’t use Grimy’s clever method! Terribly inefficient for larger input. The following version handles all of the test cases but is a byte longer:

Jelly, 9 bytes

DJRḌ÷@fⱮ9

Try it online!

\$\endgroup\$
1
\$\begingroup\$

Hy, 44 bytes

(defn a[p](print(get(str(*(+(int p)1)9))0)))

Uses Grimy's method

Try it online!

\$\endgroup\$
1
\$\begingroup\$

Keg -rr, 4 bytes

⑨9*÷

Try it online!

Of course, uses the same approach as the 05AB1E answer. Also uses the new -rr (reverse and print raw) flag.

Transpiles to:

from KegLib import *
from Stackd import Stack
stack = Stack()
printed = False
increment(stack)
integer(stack, 9)
maths(stack, '*')
item_split(stack)
if not printed:
    reverse(stack)
    raw(stack)
\$\endgroup\$
1
\$\begingroup\$

Wren, 30 bytes

Just a port of most answers.

Fn.new{|i|(i*9+9).toString[0]}

Try it online!

\$\endgroup\$
1
\$\begingroup\$

W h, 3 bytes

)9*

Explanation

)   % Increment by 1
 9* % Multiply by 9

Flag:h % Take the first item of the result
```
\$\endgroup\$
1
\$\begingroup\$

cQuents, 10 bytes

D9*_+$)[0]

Try it online!

Just another port of Grimmy's answer.

     $     # Index
   _+      # +1
 9*        # *9
D     )[0] # First digit
\$\endgroup\$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge that you have read and understand our privacy policy and code of conduct.

Not the answer you're looking for? Browse other questions tagged or ask your own question.