Teaser 3095: Diddums!
From The Sunday Times, 16th January 2022 [link] [link]
“Diddums” was Didi’s dada’s name for numbers where the number of positive DIvisors (including 1 and the number), the number of Digits, and the Digit sUM are equal.
Didi enjoyed mental arithmetic, doing it speedily and accurately. For numbers of digits from 1 to 9 she listed in ascending order all possible numbers whose digit sum equalled the number of digits. Working through her list in order, she quickly found the first two diddums (1 and 11) and the next three diddums. After many further calculations, Didi confirmed that the sixth diddum (which is even) was listed.
“Now I’m bored”, she moaned.
“Diddums!”, said Didi’s dada.
What is the sixth diddum’s digit sum?
[teaser3095]
Frits, 
GeoffR, 
Hugh+Casement, and 2 others are discussing. 
S2T2 
Jim Randell 4:49 pm on 14 January 2022 Permalink |
This Python program generates the numbers in order.
To find the first 6 numbers takes 74ms. (Internal runtime is 13ms).
Run: [ @replit ]
from enigma import (tau, irange, inf, arg, printf) # generate numbers with a digit sum of t and k digits def generate(t, k, n=0): if k == 1: if t < 10: yield 10 * n + t else: for d in irange((0 if n else 1), min(9, t)): yield from generate(t - d, k - 1, 10 * n + d) # generate "diddums" numbers in order def solve(): for k in irange(1, inf): for n in generate(k, k): if tau(n) == k: yield (k, n) N = arg(6, 0, int) # find the first N numbers for (i, (k, n)) in enumerate(solve(), start=1): printf("[{i}] {k} -> {n}") if i == N: breakSolution: The sixth number on the list has a digit sum of 8.
The list of numbers looks like this:
For the larger numbers it is more efficient to use Pollard’s Rho method [[
prime_factor_rho()]] to find prime factors, which we can do by calling [[tau()]] like this:LikeLike
GeoffR 8:41 pm on 14 January 2022 Permalink |
A brute force solution ran in about 20 sec. After the first sixth number, there were many similar solutions to the sixth number.
from enigma import nsplit, tau, divisors cnt = 0 #counter for number of diddum numbers. for k in range(1, 100000000): n = nsplit(k) #split number into digits sn = sum(n) #find sum of digits nd = len(n) #find number of digits # check sum of digits = number of digits if sn == nd: tk = tau(k) # check sum of digits = no. of divisors if sn == tk: print(f"{cnt+1}: num={k}, no. divisors={tau(k)}") print(f"Divisors are {divisors(k)}") print() cnt += 1 # stop after the 6th number if cnt == 6: breakLikeLike
NigelR 9:55 am on 15 January 2022 Permalink |
I used a very similar approach to GeoffR (a sledgehammer once again!) but without the enigma functions. I also added a fudge to exploit the ‘(which is even)’ advice for the 6th number by using an increment of 2 once the 5th number had been found. This reduced the run time by a couple of days.
import math #function to return list of digits in n def digs(n): cont = [] while n: n,a = divmod(n,10) cont.append(a) return cont #function to return list of divisors of n def divisg(n): divs = [1] for i in range(2,int(math.sqrt(n))+1): if n%i == 0: divs.extend([i,int(n/i)]) divs.extend([n]) return list(set(divs)) #main i = 0 inc = 1 count = 0 while count < 6: i += inc num = digs(i) if sum(num) != len(num): continue div = list(divisg(i)) if len(div) != len(num):continue print(i,num,div) count += 1 if count==5: if i%2 != 0: i+=1 inc=2LikeLike
Hugh+Casement 8:52 am on 16 January 2022 Permalink |
That was a giant sledgehammer, Nigel! There are faster ways. For example, the square of a prime has three integer divisors: none fits here. The cube of a prime has four divisors: again none found. The product of two different primes also has four divisors: that provides the next three (mentioned in the puzzle). The product of one prime and the square of another has six divisors; one of those primes obviously has to be 2 to give an even product.
I’ll spare you my program in Basic, but after rejecting a few numbers of factors & digits it quickly found the sixth diddums and a further five.
LikeLike
GeoffR 3:42 pm on 23 January 2022 Permalink |
This programme considers ‘Diddums’ numbers for separate three, four, five, six, seven and eight digit groups. This method produced the six-number solution with a much faster run-time than my previous posting. It ran in 28 msec.
from enigma import Primes, tau, divisors, nsplit from enigma import Timer timer = Timer('ST3095', timer='E') timer.start() # primes for 4-digit 'Diddums' numbers primes = list(Primes(200)) # Check 3,4,5,6,7,8 digit 'Diddums' numbers DD_nums = [] DD_nums.append(1) # two given 'Diddums' numbers DD_nums.append(11) # 3-digit 'Diddums' numbers D3 = [x * x for x in range(10, 20) if x * x in range(100, 301)] for n in D3: if tau(n) == 3 and sum(nsplit(n)) == 3: DD_nums.append(n) # 4-digit 'Diddums' numbers - use a and b as primes, # where four divisors are 1, a, b, a * b for a in primes: for b in primes: if a == b: continue if a * b in range(1000, 4001): if a * b in DD_nums: continue if tau(a * b) == 4 and sum(nsplit(a * b)) == 4: DD_nums.append(a * b) # 5-digit 'Diddums' numbers for powers p ^ 4, # five divisors are 1, p, p^2, p^3, p^4 for p in (11, 13, 17): num = p ** 4 if num in range(10000, 50001): if tau(num) == 5 and sum(nsplit(num)) == 5: DD_nums.append(num) # 6-digit 'Diddums' numbers # product of 2 primes in a^2 * b format gives six divisors for a in primes: for b in primes: if a == b: continue if a * a * b in range(100000, 600001): if a * a * b in DD_nums: continue if tau(a * a * b) == 6 and sum(nsplit((a * a * b))) == 6: DD_nums.append(a * a * b) # 7-digit 'Diddums' numbers for powers p^6, # seven divisors are 1, p, p^2, p^3, p^4, p^5, p^6 for p in (11, 13): num = p ** 6 if num in range(1000000, 7000001): if tau(num) == 7 and sum(nsplit(num)) == 7: DD_nums.append(num) # check first 10,000 8-digit numbers (initially) for # potential 8-digit numbers summing to eight D8 = [] for n in range(10000000, 10010000): ns = nsplit(n) if sum(ns) == 8: D8.append(n) for n in D8: if tau(n) == 8: DD_nums.append(n) break print('Diddums Numbers are ', sorted(DD_nums)) timer.stop() timer.report() # Numbers are [1, 11, 1003, 1111, 2101, 10000034] # [ST3095] total time: 0.0276404s (27.64ms)LikeLike
Frits 8:37 am on 29 June 2023 Permalink |
Only fast for this puzzle (for general purposes too slow).
Using tau(n, prime_factor_rho) wasn’t necessary.
from enigma import tau from itertools import compress sumd = lambda n: sum(int(x) for x in str(n)) def primesbelow(n): # rwh_primes1v2(n): """ Returns a list of primes < n for n > 2 """ sieve = bytearray([True]) * (n // 2 + 1) for i in range(1, int(n ** 0.5) // 2 + 1): if sieve[i]: sieve[2 * i * (i + 1)::2 * i + 1] = \ bytearray((n // 2 - 2 * i * (i + 1)) // (2 * i + 1) + 1) return [2, *compress(range(3, n, 2), sieve[1:])] # return next valid diddum def next_diddum(m, n, maxd): while m <= maxd: m += 9 if sumd(m) == n and tau(m) == n: return m return maxd + 1 # too high ds = [1, 11] # two given diddum numbers # if n = 3, 6 or 9 then a diddum can't be of the form p^(n-1) as it must be # 3 must be a divisor (3^2 = 9, 3^5 = 243 and 3^8 = 6561) # if n = 6 then a diddum can't be of the form p1 * p2**2 as p1 and p2 must # be chosen from 2 and 3 for n in [4, 5, 7, 8, 9]: maxd = n * 10**(n - 1) # maximum diddum number if n in {5, 7}: # only option p^(n-1) for prime numbers maxp = int(maxd**(1 / (n - 1))) # maximum prime number # test prime power p^(n-1), divisors are 1, p, p^2, ..., p^(n-2), p^(n-1) P = primesbelow(maxp + 1) # prime number 3 may not be used if sum digits is not divisible by 3 P = [p for p in P if not n % 3 or p != 3] ds.extend(pwr for p in [x for x in P if 10 < x <= maxp] if sumd(pwr := p**(n - 1)) == n) else: found5 = (len(ds) == 5) # initial valid diddum (start just too low) m = next_diddum(10**(n - 1) + n - 10, n, maxd) while m <= maxd: ds.append(m) if found5: print("sixth diddum's digit sum:", m) exit() m = next_diddum(m, n, maxd)LikeLike