function that counts...
in [Python]
|
From: superpollo on 20 May 2010 14:36 Grant Edwards ha scritto: > On 2010-05-20, superpollo <utente(a)esempio.net> wrote: >> Steven D'Aprano ha scritto: >>> On Wed, 19 May 2010 21:58:04 +0200, superpollo wrote: >>> >>>> ... how many positive integers less than n have digits that sum up to m: >>>> >>>> In [197]: def prttn(m, n): >>> Does the name "prttn" mean anything? I'm afraid I keep reading it as a >>> mispelling of "print n". >> pArtItIOn > > One might be tempted to suggest the name "partition". no kidding: i was afraid to use some reserved word...
From: Grant Edwards on 20 May 2010 15:53 On 2010-05-20, superpollo <utente(a)esempio.net> wrote: > Grant Edwards ha scritto: >> On 2010-05-20, superpollo <utente(a)esempio.net> wrote: >>> Steven D'Aprano ha scritto: >>>> On Wed, 19 May 2010 21:58:04 +0200, superpollo wrote: >>>> >>>>> ... how many positive integers less than n have digits that sum up to m: >>>> >>>> Does the name "prttn" mean anything? I'm afraid I keep reading it as >>>> a mispelling of "print n". >>> >>> pArtItIOn >> >> One might be tempted to suggest the name "partition". > > no kidding: i was afraid to use some reserved word... Since Python is interactive, and you don't get charged for each time you run your deck through the reader, that's easy enough to check: $ python Python 2.6.4 (r264:75706, Mar 1 2010, 10:33:43) [GCC 4.1.2 (Gentoo 4.1.2 p1.1)] on linux2 Type "help", "copyright", "credits" or "license" for more information. >>> partition Traceback (most recent call last): File "<stdin>", line 1, in <module> NameError: name 'partition' is not defined >>> sum <built-in function sum> >>> int <type 'int'> >>> file <type 'file'> Lest my allusions to Fortran IV be lost upon the less grizzled, only the first 6 characters were significant in Fortran IV identifiers, and removing all of the vowels from a longer word was an idiomatic way to create an identifier with a length <= 6. IIRC, the number 6 was originally chosen because that's how many 6-bit characters you could hold in a single 36-bit CPU register. That way when writing a compiler/link/assembly you could compare two identifiers using a single "CMP" instruction. I'm not sure why 36-bits was such a popular ALU width, but many different vendors sold 36-bit machines back in the day. -- Grant Edwards grant.b.edwards Yow! Hand me a pair of at leather pants and a CASIO gmail.com keyboard -- I'm living for today!
From: D'Arcy J.M. Cain on 20 May 2010 22:11 On Thu, 20 May 2010 19:53:42 +0000 (UTC) Grant Edwards <invalid(a)invalid.invalid> wrote: > Since Python is interactive, and you don't get charged for each time > you run your deck through the reader, that's easy enough to check: Whoa! For a moment there I thought it was 1969. :-) -- D'Arcy J.M. Cain <darcy(a)druid.net> | Democracy is three wolves http://www.druid.net/darcy/ | and a sheep voting on +1 416 425 1212 (DoD#0082) (eNTP) | what's for dinner.
From: Albert van der Horst on 21 May 2010 12:02 In article <ht4406$92c$1(a)reader1.panix.com>, Grant Edwards <invalid(a)invalid.invalid> wrote: > >Lest my allusions to Fortran IV be lost upon the less grizzled, only >the first 6 characters were significant in Fortran IV identifiers, and >removing all of the vowels from a longer word was an idiomatic way to >create an identifier with a length <= 6. > >IIRC, the number 6 was originally chosen because that's how many 6-bit >characters you could hold in a single 36-bit CPU register. That way >when writing a compiler/link/assembly you could compare two >identifiers using a single "CMP" instruction. > >I'm not sure why 36-bits was such a popular ALU width, but many >different vendors sold 36-bit machines back in the day. 16 bit mini computers were popular: the pdp11. Now 3 FORTRAN char's fitted in one word (radix 40). At least it helped to shoe horn identifier names into two words. > >-- >Grant Edwards grant.b.edwards Yow! Hand me a pair of > at leather pants and a CASIO > gmail.com keyboard -- I'm living > for today! -- -- Albert van der Horst, UTRECHT,THE NETHERLANDS Economic growth -- being exponential -- ultimately falters. albert(a)spe&ar&c.xs4all.nl &=n http://home.hccnet.nl/a.w.m.van.der.horst
From: Bryan on 21 May 2010 19:41
Peter Pearson wrote: > If it's important for the function to execute quickly for large n, > you might get a useful speedup by testing only every ninth integer, Our standards for "quickly" and "large" seem kind of thin. > I suspect that further applications of number theory would > provide additional, substantial speedups, but this wanders > away from the subject of Python. I was thinking combinatorics more than number theory. I didn't find a neat formula, but I came up with a recursive memo-izing algorithm that handles 100-digit n's. I tested this against the initial algorithm plus Peter Pearson's optimization for numbers up to several thousand, and it agrees... well, after I fixed stuff that is. -Bryan Olson # ----------- _nds = {} def ndsums(m, d): """ How many d-digit ints' digits sum to m? """ assert m >= 0 and d >= 0 if m > d * 9: return 0 if m == 0 or d == 1: return 1 if (m, d) not in _nds: _nds[(m, d)] = sum(ndsums(m - i, d - 1) for i in range(min(10, m + 1))) return _nds[(m, d)] def prttn(m, n): assert m > 0 and n > 0 def inner(m, dls): if not dls: return 1 if m == 0 else 0 count = 0 msd, rest = dls[0], dls[1:] for d in range(msd): if m >= d: count += ndsums(m - d, len(dls) - 1) count += inner(m - msd, dls[1:]) return count return inner(m, [int(c) for c in str(n - 1)]) pi100 = 3141592653589793238462643383279502884197169399375105820974944592307816406286208998628034825342117067 print(prttn(500, pi100)) |