Generate product of list with conditions

Question

I want processing large numbers with 10k+ digits, so I use tuples, because integer type cannot be used (precision of number is important, because sum of digits). There are only 2 unique digits, 9 and 0.

First condition: Modulo of sum of digits with 999 is 0.
Second condition: It is large integer number, so first digit cannot be 0.
Last condition: Last digit is 0.

My solution is:

from itertools import product

L = [10000,11000,12000]

for M in L:
    for i in product([0, 9], repeat=M):
        if i[0] != 0 and i[-1] == 0:
            s = sum(i)
            if s % 999 == 0:
                print (s)

Is possible count number of generated values with these conditions? Is possible change solution/another solution(s) for reduce time of generating expected output, e.g. generate only digits with sum of digits is more like 999? I am thinking about Decimal, but here is problem with sum of digits. Order of generated numbers (tuples, arrays) is not important.

It is so huge tuples, so problematic easy testing.I try create some sample (not idea if useful):

for i in product([9, 0], repeat=20):
    if i[0] != 0 and i[-1] == 0:
        s = sum(i)
        if s % 99 == 0:
            print (i, s)

Answer 1

The number of such possible numbers would be too large to generate all.

Let's call L the number of digits in your number, and n the number of 9.

Modulo of sum of digits with 999 is 0 means that: n*9 = m*999, so n = k*111 where k is an integer.

The first digit is 9, and the last is 0, so there are L-2 places left to put the remaining (k*111 - 1) 9 digits.

So, the number of such numbers is the sum of the number of combinations ( (L-2) choose (k*111-1) ) for k between 1 and int((L-1)/111))

So, a possible code:

import operator as op
from functools import reduce

# From https://stackoverflow.com/questions/4941753/is-there-a-math-ncr-function-in-python
def ncr(n, r):
    r = min(r, n-r)
    numer = reduce(op.mul, range(n, n-r, -1), 1)
    denom = reduce(op.mul, range(1, r+1), 1)
    return numer // denom  # Changed for integer division

def possible_numbers(L):
    return sum(ncr(L-2, 111*k - 1) for k in range(1, (L-1)//111))

print(possible_numbers(10000))

# 46506588317635469366401415658013639152242514965252855714041144018498987152707044490194457854465305060020773686383485941436739496916009717012616366376246414571169910310699834725291436347258613064146124967400646078243663290971123135369040450765747850207912640778375391521167004887068454467534692885571315434928724105198818380334746555427574950364615165695566283976630032289652540054620732064526597228268611847676696899672765577347754597526393233231013911103228183531257080334315932738035622562131489280570776426153110319970303630143757955230868260221372217820886676391878309046535523092899792732603384686832015291205699914402933832273424671204699396414708887671531202101527299797220557526495935874078061714541726044022824401127277289199364810083989340886903060879319068042995827037751119856277555325118818012910801413269671414202747818363564693812789991123599795926600974448559896232026533659303781683288750777356519373140416641070335357434342957815577446771837059264519071351111701743419392138893923198793667574531536322827159764885405347516087975885606826893886851504292563461335005149974908491745377479301673268815242719993061641393932755789000155034631404392298259100662543152918803846714114697300923960523557500317195566759812657273510052876469933988067730551693799653175259045326679352888837840615599025061763546193617710870648379633919635058872421276909819607798170545658257733866028814603688331134993133516485082037147925444085128568947517112262094010118995477748614613681297345233932152146172358997240155349554049974584904754905949454881684316277423691704957916937555749917546766207774972493217477043714652995265409684903579726779500656471405514359721102426435531185506178592945522184727847016844486420511644284474508534529688998209007331208512957982383305010070433027822069432758467560863914508655552438978200137331142103777139831138329641584247585016869654053739406398693488384069254725347054264531039092260379613683402826431841651702016107570078218034751759156452991362380781969813524106141836783707976391132433066632109509663706711194120392913346984831497576260954280288258157219236029228818152608039675500130313183928069363862241906263121908112579346403564641214804122206420758371341181045355185272831160085528848859295608701517219671599684543743252593692174235989978345204406049350779297271034684859111097644033128750102959471412294900623227232358717924727059914175333714529865811974930107943791917826273949743788824216294023431731389259674185985763199421896541289618952210976760618905706699064025869740093553019041859274291091877197046340635783795996884883288761816361022414903437664468405527174106098428305866565043923442930029525366818247447766037463650273567442968538251684623455304412633953426243893756890813731429721493555818339963997009857257028373522283512536995315377100044676823672536566066483879259428166867133820082490868856820190168040370122307493700971959637546773031509327007856264111997525714829526125911250334270232166355120078967567596110824407335535205220718583123846127299455

# It's 3008 digits long....

Answer 2

Less mathematical solution would be using dynamic programming:

M = 1000
cache = {}

def dp(i, v, sum_of_digits):
  if(i == M-1):
    return sum_of_digits % 999 == 0 and v == 0

  if((i, sum_of_digits) in cache):
    return cache.get((i, sum_of_digits))

  result = dp(i + 1, 0, sum_of_digits) + dp(i + 1, 9, sum_of_digits + 9)
  cache[(i, sum_of_digits)] = result
  return result


print(dp(0, 9, 9))

Output:

281853033550040537904406694735205583322614867369419355514834998793657889372557150681302072580895266688090267034276630517914503707145674628565136259594047883519869400688956077638702940707076342539608905721192230524534619011898800645140130344499642277977871480846234887754725793524573506157312565257

Explanation:

Dynamic programming algorithm works by memoizing the sub-results it gets. In our case it is the cache dict who store the sub-results.

At each invocation we have two possibilities: 1) either the next digit is 0; so we do not increase sum_of_digits; 2) or it is 9; so we increase the sum_of_digits.

At each invocation we memoize the results we get by summing the two sub results: dp(i + 1, 0, sum_of_digits), dp(i + 1, 9, sum_of_digits + 9).

we terminate when there is M number of digits, returning True if sum_of_digits modulo 999 is 0 and last digit v is 0.

Note we do not check for the first digit because, we always have 9 as the first digit dp(0, 9, 9).

Note:

1. you may need to increase maximum recursion depth using:

   sys.setrecursionlimit(XXXXXX..)

   or you can transform the recursive solution to iterative(it is always possible to do that).

2. Although this solution is more efficient than the brute-force solution, @Thierry_Lathuille is more efficient than this solution,.