OFFSET
1,4
COMMENTS
From Chai Wah Wu, Dec 04 2015, Nov 03 2018: (Start)
If n > 3 and n == 0 (mod 3) then a(n) = 0 since the digit sum is a multiple of 3.
Primes with digit product maximal among all numbers with the same digit sum (not just maximal among primes) only contain the digits 2, 3 or 4. A digit 0 leads to a digit product 0 which is not maximal. A digit 1 with another digit d (since 1 is not prime, there must be another digit d) can be replaced with the digit d+1 (if d < 9) which preserves the digit sum, but strictly increases the digit product (if d = 9, 1 and 9 can be replaced with 3, 3 and 4 which again increases the digit product). For a digit d > 4, there is a series of digits from the set {2,3,4} whose sum is d and whose product is strictly larger than d. For instance, 5 -> {2,3} whose product is 6. 6 -> {3,3}, 7 -> {3,4}, 8 -> {2,3,3}, 9 -> {3,3,3}. Thus the digit d in a number can be replaced with digits 2, 3, 4 to obtain a number with the same digit sum and a larger digit product. Furthermore, the digits 2 and 4 cannot both appear, the digit 2 cannot appear more than twice and the digit 4 cannot appear more than once since {3,3} also sums to 6 and has product 9 > 8.
This analysis implies the following for n > 3. If n == 1 (mod 3), then primes with maximal digit product among all numbers with the same digit sum (if they exist) have digits 3 and either two digits 2 or a single digit 4. If n == 2 (mod 3), then primes with maximal digit product among all numbers with the same digit sum (if they exist) have digits 3 and a single digit 2. Values for n for which such primes do not exist are 4, 38, 46, 65, 94, ... In these cases a(n) can still be > 0, but the digit product of these primes is not maximal among all numbers with digit sum n. So far, it seems that in these cases (except for n = 4) these primes also only contain the digits 2, 3, or 4.
(End)
LINKS
Chai Wah Wu, Table of n, a(n) for n = 1..802
EXAMPLE
a(19)=8 and a(20)=2 because we respectively have the 8 primes 333433, 334333, 343333, 2332333, 2333323, 3223333, 3233323, 3332233 all with a maximal digit product of 3^5*2^2 = 972 for a digit sum of 19 and the 2 primes 3233333, 3333233 with maximal digit product 3^6*2 = 1458 for digit sum 20.
MATHEMATICA
Needs["Combinatorica`"]; Table[If[And[n > 3, Divisible[n, 3]], 0, Length@ MaximalBy[Select[FromDigits /@ Flatten[Map[Permutations, Combinatorica`Partitions@ n], 1] /. x_ /; EvenQ@ x -> Nothing, PrimeQ], Times @@ IntegerDigits@ # &]], {n, 24}] (* Michael De Vlieger, Dec 11 2015, Version 10 *)
CROSSREFS
KEYWORD
nonn,base
AUTHOR
Lekraj Beedassy, Apr 05 2008
EXTENSIONS
a(25) and a(28) corrected and a(29)-a(83) added by Chai Wah Wu, Nov 30 2015
STATUS
approved