# Perl Weekly Challenge: Represent Integer

by Abigail

## Challenge

You are given a positive integer $N and a digit $D.

Write a script to check if $N can be represented as a sum of positive integers having $D at least once. If check passes print 1 otherwise 0.

### Example

Input: $N = 25,$D = 7
Output: 0 as there are 2 numbers between 1 and 25 having the digit 7
i.e. 7 and 17. If we add up both we don't get 25.

Input: $N = 24,$D = 7
Output: 1


## Discussion

We could solve this by recursion and brute force trying to find a set of numbers which to the given target number. Which will work for the baby examples with tiny, tiny numbers typical of the Perl Weekly Challenge, but would be absolutely madness for larger numbers.

Instead we will first prove that most numbers can be written as a sum of integers each containing a specific digit, and then we will prove which of the remaining numbers can.

A positive integer containing a digit $$d$$ is called a $$d$$-number.

A positive integer which can be written as a sum of $$d$$-numbers is called a $$d$$-composable number.

$$N$$ is $$d$$-composable if $N \geq \begin{cases} 100, & d = 0 \\ d \cdot 10, & d \geq 1 \end{cases}$

Let's first consider the case that $$d = 0$$. If $$N \geq 100$$ then we can write $$N = 100 + i + k \cdot 10$$, with $$i = N \mod 10$$, and $$k = \frac{N - 100 - i}{10}$$.

This means we can write $$N = (100 + i) + 10 + \ldots + 10$$, where we have a $$10$$ $$k$$ times. Since $$0 \leq i < 10$$, $$100 + i$$ contains a $$0$$, and so does $$10$$. Hence, any $$N \geq 100$$ is $$0$$-composable.

If $$d > 0$$ and $$N \geq 10 \cdot d$$, then we can write $$N = 10 \cdot d + i + k \cdot d$$, with $$i = N \mod d$$, and $$k = \frac{N - 10 \cdot d - i}{d}$$.

This means we can write $$N = (10 \cdot d + i) + d + \ldots + d$$, where we have a $$d$$ $$k$$ times. Since $$0 \leq i < d$$, $$10 \cdot d + i$$ is a two digit number starting with a $$d$$. Hence, any $$N \geq 10 \cdot d$$ is $$d$$-composable.

$$N < 100$$ is $$0$$-composable iff $$N$$ is a multiple of $$10$$.

All the $$0$$-numbers less than $$100$$ are multiples of $$10$$.

For $$d > 0$$, $$N < 10 \cdot d$$ is $$d$$-composable, iff $$N = 10 \cdot c + d \cdot k$$, for some $$0 \leq c < \frac{d}{\text{gcd}(d, 10)}$$.

Let $$g = \frac{d}{\text{gcd}(d, 10)}$$.

If $$N < 10 \cdot d$$, then $$N$$ has at most two digits. It follows from the definition that if $$N$$ is $$d$$-composable, then $N = \sum_{i = 0}^{d-1} a_i \cdot (10 \cdot i + d) = 10 \cdot \sum_{i = 0}^{d-1} (a_i \cdot i) + d \cdot \sum_{i = 0}^{d-1} a_i$

Let $$c' = \sum_{i = 0}^{d-1} (a_i \cdot i)$$ and $$k' = \sum_{i = 0}^{d-1} a_i$$, hence, $$N = 10 \cdot c' + d \cdot k'$$, for some integers $$0 \leq c' < d, 0 < k'$$.

Now, $$c' = c'' + b \cdot g$$ so that $$c'' < g$$ (it's possible that $$b = 0$$). Hence, $$N = 10 \cdot c'' + 10 \cdot b \cdot g + d \cdot k'$$. Since $$g = \frac{d}{\text{gcd}(d, 10)}$$, $$10 \cdot g$$ is a multiple of $$d$$. So, $$10 \cdot g = d \cdot k''$$ for some integer $$k'' \geq 0$$. Plugging this in, we get $$N = 10 \cdot c'' + d \cdot (k' + b \cdot k'')$$. Since $$k' > 0$$, we have $$N = (10 \cdot c'' + d) + d + \ldots + d$$, where the number of $$d$$s is $$k' - 1 + b \cdot k''$$. $$10 \cdot c'' + d$$ is a one or two digit number containing a $$d$$.

Picking $$c = c''$$ and $$k = k' + b \cdot k''$$ proofs our claim.

As an example, the table below shows all $$7$$-composable numbers below $$70$$, and the break down according to the formula above:

$\begin{array}{rcrcl} 7 & = & & & 7 \\ 14 & = & & & 7 + 7 \\ 17 & = & 17 & & \\ 21 & = & & & 7 + 7 + 7 \\ 24 & = & 17 & + & 7 \\ 27 & = & 27 & & \\ 28 & = & & & 7 + 7 + 7 + 7 \\ 31 & = & 17 & + & 7 + 7 \\ 34 & = & 27 & + & 7 \\ 35 & = & & & 7 + 7 + 7 + 7 + 7 \\ 37 & = & 37 & & \\ 38 & = & 17 & + & 7 + 7 + 7 \\ 41 & = & 27 & + & 7 + 7 \\ 42 & = & & & 7 + 7 + 7 + 7 + 7 + 7 \\ 44 & = & 37 & + & 7 \\ 45 & = & 17 & + & 7 + 7 + 7 + 7 \\ 47 & = & 47 & & \\ 48 & = & 27 & + & 7 + 7 + 7 \\ 49 & = & & & 7 + 7 + 7 + 7 + 7 + 7 + 7 \\ 51 & = & 37 & + & 7 + 7 \\ 52 & = & 17 & + & 7 + 7 + 7 + 7 + 7 \\ 54 & = & 47 & + & 7 \\ 55 & = & 27 & + & 7 + 7 + 7 + 7 \\ 56 & = & & & 7 + 7 + 7 + 7 + 7 + 7 + 7 + 7 \\ 57 & = & 57 & & \\ 58 & = & 37 & + & 7 + 7 + 7 \\ 59 & = & 17 & + & 7 + 7 + 7 + 7 + 7 + 7 \\ 61 & = & 47 & + & 7 + 7 \\ 62 & = & 27 & + & 7 + 7 + 7 + 7 + 7 \\ 63 & = & & & 7 + 7 + 7 + 7 + 7 + 7 + 7 + 7 + 7 \\ 64 & = & 57 & + & 7 \\ 65 & = & 37 & + & 7 + 7 + 7 + 7 \\ 66 & = & 17 & + & 7 + 7 + 7 + 7 + 7 + 7 + 7 \\ 67 & = & 67 & & \\ 68 & = & 47 & + & 7 + 7 + 7 \\ \end{array}$

## Solution

Given the lemmas above, we come to the following algorithm:

• If $D == 0, we output 1 if $N >= 100 or $N % 10 == 0, and 0 otherwise. • If $D > 0, then:
• If $N >= 10 *$D, we output 1, else
• We iterate $i from 0 up to (but not including) the greatest common divisor of $D and 10:
• If ($N - 10 *$i - $D) is not negative, and a multiple of $D, we output 1, and exit the loop.
• If we did not produce any output, we output 0.

We will use an predefined array with the greatest common divisors of 10 and the numbers 1 to 9; those values are: 1, 2, 1, 2, 5, 2, 1, 2, 1.

### Perl

Predefined array with greatest common divisors:

my @gcds = (0, 1, 2, 1, 2, 5, 2, 1, 2, 1);


my ($N,$D) = split;


Handling the case of $D == 0: if ($D == 0) {
say $N >= 100 ||$N % 10 == 0 ? 1 : 0;
exit;
}


Handling the case where $N >= 10 *$D:

if ($N >=$D * 10) {
say 1;
exit;
}


The other cases:

for (my $i = 0;$i < $D /$gcds [$D];$i ++) {
my $T =$N - 10 * $i -$D;
if ($T >= 0 &&$T % \$D == 0) {
say 1;
exit;
}
}
say 0;


Find the full program on GitHub.

### Other languages

The above algorithm translates practically one to one to each of the other languages we implemented the solution in: AWK, Bash, C, Lua, Node.js, Python, and Ruby.