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....