S2T2

Jim Randell 8:00 am on 10 June 2021 Permalink Reply
Tags: by: Graham Smithers ( 82 )   

• 

  Jim Randell 8:00 am on 10 June 2021 Permalink | Reply

  Using : for concatenation, we have:

  D:abc:z = D × abc:D:z
  ⇒ 10^(D − 1) D + 10 abc + z = D (100 abc + 10 D + z)
  ⇒ abc = (10 D (10^(D − 2) − D) − (D − 1) z) / (100 D − 10)

  where abc represents a (D − 2) digit number).

  This Python program runs in 50ms.

  Run: [ @replit ]

  from enigma import irange, div, ndigits, printf
  
  # choose D
  for D in irange(3, 9):
    x = 10 * D * (10 ** (D - 2) - D)
    y = 100 * D - 10
    # possible final digits
    for z in irange(0, 9):
      # note: D * z = z [mod 10]
      r = (D - 1) * z
      if not(r % 10 == 0): continue
      # calculate abc...
      abc = div(x - r, y)
      if abc is None or ndigits(abc) != D - 2: continue
      # output solution
      printf("number={abc}{D}{z} [D={D}]")
  

  Solution: The number you started with is 101123595.

  So, D = 9, and: 9 × 101123595 = 910112355.

  LikeLike

  • 

    Frits 12:15 pm on 10 June 2021 Permalink | Reply

    @Jim, you also could have used (regarding the r % 10 == 0) :

    for z in [0, 2, 4, 5, 6, 8]:
    

    LikeLike

  • 

    Jim Randell 2:57 pm on 10 June 2021 Permalink | Reply

    If we construct numbers by taking successive digits of the larger number (D:abc:z), and divide these by D, then we get the corresponding digits of the number we started with, which can then be used in the next division to determine the following digit:

    D / D = a (so: a = 1)
    Da / D = ab (so: b = 0)
    Dab / D = abc
    …

    So, for a given value of D, we can compute successive digits of abc. And after the (D − 2) digits are calculated, z is chosen to complete the division, and then we check that it is a viable digit:

    from enigma import irange, div, printf
    
    # choose D
    for D in irange(3, 9):
      n = D
      x = 0
      # perform (D - 2) divisions
      for _ in irange(1, D - 2):
        d = (n // D) % 10
        n = 10 * n + d
        x = 10 * x + d
    
      # the final digit is z
      n = 10 * n
      x = 100 * x + 10 * D
      z = div(n - x * D, D - 1)
      if z is None or z < 0 or z > 10: continue
    
      # output solution
      n += z
      x += z
      printf("[D={D}] {x} * {D} = {n}")
    

    This appears to be slightly faster than my original code (internal runtime is reduced from 60μs to 42μs).

    LikeLike

• 

  Frits 11:57 am on 10 June 2021 Permalink | Reply

  We can also continue the analysis, so C must be 1, etc …

  from enigma import SubstitutedExpression
  
  # the alphametic puzzle
  p = SubstitutedExpression(
    [# consider number ABCDEFGHI
     
     # (9 * H + carry digit) modulo 10 must be equal to G
     "(81 + 0.8 * I) % 10 = G",
  
     # we have established H must be 9   
     "HABCDEFGI == 9 * ABCDEFGHI",
     ],
  
    answer="ABCDEFGHI",
    verbose=0,
    # (9 * I) % 10 = I so I is 0 or 5
    # Consider 9 * FGHI = HFGI (F > 0), this can only happen when H is 9
    # so H is 9, A must be 1 and B must be 0
    # G is 1 or 5 (see G formula)
    d2i=dict([(0, "AH")] + [(1, "BHI")] + [(2, "ABHI")] + [(5, "ABH")] + 
             [(k, "ABHI") for k in [3, 4, 6, 7, 8, 9]] +
             [(9, "ABI")]),
    distinct="",   # allow variables with same values
    reorder=0,
  )
  
  # Print answer
  for (_, ans) in p.solve():
    print(f"{ans}")
  

  LikeLike

• 

  GeoffR 1:53 pm on 10 June 2021 Permalink | Reply

  A simple solution in MiniZinc, using Frits analysis i.e. D-digit number = 9

  
  % A Solution in MiniZinc
  
  var 0..9: A; var 0..9: B; var 0..9: C; var 0..9: D; var 0..9: E;
  var 0..9: F; var 0..9: G; var 0..9: H; var 0..9: I;
  
  constraint H > 0 /\ A > 0;
  
  var 100000000..999999999: ABCDEFGHI = I + 10*H + 100*G + 1000*F + 10000*E
  + 100000*D + 1000000*C + 10000000*B + 100000000*A;
  
  var 100000000..999999999: HABCDEFGI = I + 10*G + 100*F + 1000*E + 10000*D
  + 100000*C + 1000000*B + 10000000*A + 100000000*H;
  
  constraint HABCDEFGI == 9 * ABCDEFGHI;
  
  solve satisfy;
  
  output["The number you started with was " ++ show(ABCDEFGHI) ];
  
  % The number you started with was 101123595
  % time elapsed: 0.20 s
  % ----------
  % ==========
  
  

  LikeLike

  • 

    Frits 7:20 pm on 10 June 2021 Permalink | Reply

    Unfortunately my analysis was incorrect (I mixed things up).
    Following program works well with Geocode but gives no answer with the Chuffed solver.

    Using “var 0..9: A;” gives an out of range error.

    % A Solution in MiniZinc
     
    var 0..1: A; var 0..9: B; var 0..9: C; var 0..9: D; var 0..9: E;
    var 0..9: F; var 0..9: G; var 0..9: H; var 0..9: I;
    
     % moving the penultimate digit to the left so that it becomes
     % the first digit
    constraint H > 2;
     
    var 100000000..999999999: ABCDEFGHI = I + 10*H + 100*G + 1000*F
    + 10000*E + 100000*D + 1000000*C + 10000000*B + 100000000*A;
     
    var 10000000..99999999: ABCDEFGI = I + 10*G + 100*F + 1000*E
    + 10000*D + 100000*C + 1000000*B + 10000000*A;
     
    constraint H * pow(10, H - 1) + ABCDEFGI == H * ABCDEFGHI;
     
    solve satisfy;
     
    output["The number you started with was " ++ show(ABCDEFGHI)];
    

    LikeLike