If we multiply the integer      `717 (n)` by `7 (k)`, the result will be equal to `5019`.

Consider all the possible ways that this last number may be split as a string and calculate their corresponding sum obtained by adding the substrings as integers. When we add all of them up,... surprise, we got the original number `717`:

```
Partitions as string                Total Sums
['5', '019']                        5 + 19 = 24
['50', '19']                       50 + 19 = 69
['501', '9']                      501 + 9 = 510
['5', '0', '19']                5 + 0 + 19 = 24
['5', '01', '9']                 5 + 1 + 9 = 15
['50', '1', '9']                50 + 1 + 9 = 60
['5', '0', '1', '9']         5 + 0 + 1 + 9 = 15
                            ____________________
                              Big Total:    717
                            ____________________
```
In fact, `717` is one of the few integers that has such property with a factor `k = 7`.

Changing the factor `k`, for example to `k = 3`, we may see that the integer `40104` fulfills this property.

Given an integer `start_value` and an integer `k`, output the smallest integer `n`, but higher than `start_value`, that fulfills the above explained properties.

If by chance, `start_value`, fulfills the property, do not return `start_value` as a result, only the next integer. Perhaps you may find this assertion redundant if you understood well the requirement of the kata: "output the smallest integer `n`, but higher than `start_value`"

The values for `k` in the input may be one of these: `3, 4, 5, 7`

### Features of the random tests

If you want to understand the style and features of the random tests, see the *Notes* at the end of these instructions.

The random tests are classified in three parts.

- Random tests each with one of the possible values of `k` and a random `start_value` in the interval `[100, 1300]`
- Random tests each with a `start_value` in a larger interval for each value of `k`, as follows:
 - for `k = 3`, a random `start value` in the range `[30000, 40000]`
 - for `k = 4`, a random `start value` in the range `[2000, 10000]`
 - for `k = 5`, a random `start value` in the range `[10000, 20000]`
 - for `k = 7`, a random `start value` in the range `[100000, 130000]`
- More challenging tests, each with a random `start_value` in the interval `[100000, 110000]`.



See the examples tests.

Enjoy it.

# Notes:

- As these sequences are finite, in other words, they have a maximum term for each value of k, the tests are prepared in such way that the `start_value`  will always be less than this maximum term. So you may be confident that your code will always find an integer.

- The values of `k` that generate sequences of integers, for the constrains of this kata are: 2, 3, 4, 5, and 7. The case `k = 2` was not included because it generates only two integers.

- The sequences have like "mountains" of abundance of integers but also have very wide ranges like "valleys" of scarceness. Potential solutions, even the fastest ones, may time out searching the next integer due to an input in one of these valleys. So it was intended to avoid these ranges.

Javascript and Ruby versions will be released soon.

Source: codewars | Difficulty: EASY
Tags: Matrices

Fundamentals

Data structures

Mathematics

Starter code: def next_higher(start,k):
	

Solutions:
def sum_part(n):
	(m, p, q, r, s) = (1, 1, 1, 0, n)
	while n > 9:
		(n, d) = divmod(n, 10)
		r += d * p
		p *= 10
		if d:
			m = 1
		else:
			m *= 2
		s += q * n + m * memo[r]
		q *= 2
	return s
from collections import defaultdict
qualified = defaultdict(list)
memo = {n: n for n in range(10)}
for n in range(10, 10 ** 6):
	memo[n] = sum_part(n)
	if memo[n] > n:
		(k, r) = divmod(n, memo[n] - n)
		if not r:
			qualified[k].append(memo[n] - n)
from bisect import bisect

def next_higher(n, k):
	return qualified[k][bisect(qualified[k], n + 1)]


import itertools
from itertools import count

def break_down(text):
	numbers = text.split()
	ns = list(range(1, len(numbers[0])))
	for n in ns:
		for idxs in itertools.combinations(ns, n):
			yield [''.join(numbers[0][i:j]) for (i, j) in zip((0,) + idxs, idxs + (None,))]

def next_higher(start_value, k):
	r = 0
	for n in count(start_value + 1):
		desire = n * k
		for a in break_down(str(desire)):
			r += sum([int(b) for b in a])
		if r == n:
			return r
		r = 0


from itertools import count

def next_higher(start, k):

	def parts(n, s, p, store):
		if sum(store) > n:
			return
		if not s:
			if len(p) > 1:
				store.append(sum(p))
			return
		for i in range(1, len(s) + 1):
			parts(n, s[i:], p + [int(s[:i])], store)
		return store
	for m in count(start + 1):
		x = parts(m, str(m * k), [], [])
		if sum(x) == m:
			return m


def check(n):
	(r, l) = (0, 0)
	while n:
		(n, v) = divmod(n, 10)
		x = 0
		for i in range(l):
			x += 10 ** i * 2 ** (l - i - 1)
		r += r + v * x + v * 10 ** l
		l += 1
	return r

def next_higher(start_value, k):
	for i in range(start_value + 1, start_value + 30000):
		if check(i * k) - i - i * k == 0:
			return i


from bisect import bisect_right

def next_higher(start_value, k):
	d = {3: [162, 378, 756, 1161, 1206, 1611, 1989, 34992, 35208, 35388, 37332, 37548, 37728, 40104, 72972, 73152, 75312, 75492, 75708, 77652, 77832, 77868, 78048, 80208, 80388, 113256, 115596, 115812, 117972, 118152, 118368, 120312, 120492, 120708, 155916], 4: [198, 260, 276, 520, 536, 552, 796, 812, 1072, 1108, 1368, 1384, 1644, 1680, 1940, 1956, 2216, 2232, 2492, 10728, 10872, 79536, 109008, 110592, 140064, 193488], 5: [108, 171, 846, 1692, 4212, 14724, 18936, 19224, 20304, 103608, 123912, 148608, 168912], 7: [717, 861, 1005, 1149, 1158, 1293, 1302, 1431, 14308, 14316, 28624, 28632, 28716, 42948, 43024, 43032, 57264, 57272, 57348, 57432, 71664, 71672, 71748, 85988, 86064, 86072, 86148, 100388, 100464, 100472, 101448, 114704, 114788, 114864, 114872, 115764, 115772, 129104, 129188, 130088, 130164, 130172]}
	return d[k][bisect_right(d[k], start_value)]


from itertools import combinations, chain, count
from functools import lru_cache

def segmentations(a):

	def split_at(js):
		i = 0
		for j in js:
			yield a[i:j]
			i = j
		yield a[i:]
	r = range(1, len(a))
	for k in r:
		for sep in combinations(r, k):
			yield split_at(sep)

@lru_cache(maxsize=None)
def value(x, k):
	return sum((int(''.join(L)) for L in chain.from_iterable(segmentations(str(x * k)))))

def next_higher(start_value, k):
	return next((x for x in count(start_value + 1) if x == value(x, k)))


m = {3: [162, 378, 756, 1161, 1206, 1611, 1989, 34992, 37438, 37548, 37332, 37728, 40104, 113256], 4: [198, 260, 520, 796, 1072, 1108, 1368, 2216, 10728, 109008], 5: [171, 198, 846, 1692, 14724, 18936, 20304], 7: [717, 861, 1005, 1149, 1293, 101448, 114704, 129104, 123912]}

def next_higher(n, k):
	print(n, k)
	return next((s for s in m[k] if s > n), -1)


def partitions(s):
	if s:
		for i in range(1, len(s) + 1):
			for p in partitions(s[i:]):
				yield ([s[:i]] + p)
	else:
		yield []

def add_values(product_string):
	product_list = partitions(product_string)
	return sum([sum(map(int, items)) for items in list(product_list)[:-1]])

def next_higher(start_value, k):
	product = (start_value + 1) * k
	while add_values(str(product)) != start_value:
		start_value += 1
		product = start_value * k
	return start_value