Are numbers among the elements of a sequence of numbers of natural numbers?

Any positive integer is part of the sequence of natural numbers, so the digits of this number will be included in the sequence of digits of natural numbers.

If it is not required to find the minimum index of the occurrence in the sequence, then it is even possible to come up with a closed formula to find the index where the given number is located (see below).

It is possible to exploit the periodicity in the input number in order to find an approximate place where the search should be carried out if exactly the smallest index is needed.

For example, if the digits of a number form a sequence:

 [d, d+1, d+2, d+3] 

It is immediately clear that the smallest index is at the very beginning of the sequence (one-digit natural numbers):

 1 2 3 4 5 6 7 8 9 

If input (period = 1):

 [d, x, d+1, x] 

then the index, among the digits formed by successively going two-digit natural numbers.

If the input looks like (period = 2):

 [x,y,d,x,y,d+1] 

That number can be formed by three-digit numbers, and so on.

An example from the question: 22324 looks like the second case (period = 1): [d,x,d+1,x,d+2] —this says that the number is in the region of two-digit numbers that start at x=2 and intersects with digits of the subsequence n , n+1 , n+2 , where n=22 . Therefore, the answer for 22324 is the index of the first digit n in the sequence of the question plus the index where the input number in n begins.

If k , the number of digits in n , then the index n is: sum((j+1)*9*10**j for j in range(k)) + (n-10**(k-1))*k (the number of digits required for all numbers with a smaller number of digits ( <k ) plus the number of digits with the same number (k) that precede n ). The sum can be rewritten as a formula without a loop .

For n=22 : 9+(22-10)*2

Therefore, the answer is 33+1 for 22324. You can check it:

 >>> import itertools >>> g = (digit for number in itertools.count(1) for digit in map(int, str(number))) >>> digits = 2, 2, 3, 2, 4 >>> i=9+(22-10)*2 + 1; list(itertools.islice(g, i, i+len(digits))) [2, 2, 3, 2, 4] 

+1 is the offset inside n , where the digits begin in this case.

If the number of digits at the input is small, then the period can be found simply by looking inside the number (base log n, which is much better than iterating over the sequence n log n ). When the number contains a transition between digits, for example: 8192021 , which corresponds to the sequence 18 19 20 21 possible to process as a special case (by the presence of 9 and / or 0).

You can do without special cases and try all possible starting positions in n and all possible sizes n . This approach also does not require iteration of the sequence.

To find the minimum index in the sequence of digits of natural numbers where the given number occurs:

 def find_min_index(number): # O(k**4) if get_digits() is O(k**2) (due to str(number)) digits = get_digits(number) k = len(digits) # number of digits # find minimal n and start,end such that digits = # = get_digits(n)[start:] + get_digits(n+1) + ... + get_digits(n+m)[:end] # brute force approach for ndigits_in_n in range(1, k): # m ~ k / ndigits_in_n for start in range(ndigits_in_n): i = ndigits_in_n - start # where (n+1) starts in *digits* # is10pow = (10**ndigits_in_n == (n+1)) is10pow = same_start(digits[i:i + ndigits_in_n + 1], [1] + [0] * ndigits_in_n) # get_digits(n+1) == digits[i:i+ndigits_in_n+is10pow] end = i + ndigits_in_n + is10pow if end <= k: # enough space for all digits of (n+1) in *digits* n = digits2number(digits[i:end]) - 1 elif start == 0: # all digits of n are in *digits* n = digits2number(digits[:ndigits_in_n]) else: continue #NOTE: assume at least one of n or n+1 is in *digits* as a whole if matched_n(digits, n, start): return get_index(n) + start return get_index(number) # m == 0 

Example:

 >>> find_min_index(22324) 34 # верно 

where get_digits(number) returns the digits for the transferred number:

 def get_digits(number): """ >>> get_digits(22324) [2, 2, 3, 2, 4] """ return list(map(int, str(number))) # NOTE: O(k**2) in CPython 

and digits2number(digits) performs the inverse operation: returns the number corresponding to the transferred digits:

 import functools def digits2number(digits): """ >>> digits2number([1,2,3]) 123 """ return functools.reduce(lambda number, digit: 10 * number + digit, digits) 

same_start(L1, L2) determines whether the sequences start the same way — all the corresponding elements must be equal, but the length may differ:

 def same_start(L1, L2): """Whether L1[:k] == L2[:k] where k = min(len(L1), len(L2))""" return all(a == b for a, b in zip(L1, L2)) 

matched_n(digits, n, start) checks whether the transferred digits digits at the specified place in the sequence of digits of natural numbers — the place is specified using the natural number n and the position in it start :

 import itertools def matched_n(digits, n, start): """Check whether *digits* = = get_digits(n)[start:] + get_digits(n+1) + ... + get_digits(n+m)[:end] """ g = (digit for number in itertools.count(n + 1) for digit in get_digits(number)) return same_start(digits, itertools.chain(get_digits(n)[start:], g)) 

get_index(number) returns the position of the digits of the natural number in the sequence in question:

 def get_index(number): """sum((j + 1) * 9 * 10**j for j in range(k - 1)) + (n - 10**(k - 1)) * k >>> get_index(22) 33 """ k = ndigits10(number) - 1 return ((9 * k - 1) * 10**k + 1) // 9 + (number - 10**k) * (k + 1) 

where ndigits10(number) returns how many digits in the decimal system are needed to represent the transmitted natural number :

 import math def ndigits10(number): """The number of decimal digits in the natural *number*. >>> ndigits10(1) 1 >>> ndigits10(99) 2 >>> ndigits10(100) 3 >>> ndigits10(101) 3 """ assert number > 0 # 10**(k-1) <= number < 10**k return math.floor(math.log10(number)) + 1 

Q: What is is10pow? What is this for?

In Python, True == 1 and 0 == False .

is10pow says whether (n+1) power of tens. The purpose of the variable is to understand whether the number of digits in n and n+1 is equal. The number of digits in (n+1) always ndigits_in_n + is10pow , that is, either it is equal to the number of digits in n or one more.

Example:

• n=98 , then ndigits10(n) == ndigits10(n+1) == 2
• n=99 , then ndigits10(n) == (ndigits10(n+1) - 1) == 2

The first cycle is a brute force in numbers,
the second is a search for each number for consistency,
i is the difference to go through

The outer loop goes through all possible sizes of a n number: ndigits_in_n is the number of digits in n .

The nested loop iterates over all possible starting positions in the digits n . In your example, 22324 starts with the second digit ( start=1 ).

i is the index where (n+1) digits begin at the given digits .

Assigning the code to ndigits_in_n over all candidates for n , which are possible with given ndigits_in_n , start , digits , to find the n for which you are running:

 get_digits(n)[start:] == digits[:i] get_digits(n+1) == digits[i:i+ndigits_in_n+is10pow] digits == get_digits(n)[start:] + get_digits(n+1) + ... + get_digits(n+m)[:end] 

If not found, then the index for the number itself is returned (all digits to the same natural number refer and this number is equal to number ).