Sunday Times Teaser 2994 – Consecutive Sums

by Bill Kinally

Published Sunday February 09 2020 (link)

Amelia noticed that 15 is equal to 1+2+3+4+5 or 4+5+6 or 7+8, so there are three possible ways that it can be expressed as the sum of consecutive whole numbers. She then told Ben that she had found a three-digit number which can be expressed as the sum of consecutive whole numbers in just two different ways. “That’s interesting”, said Ben. “I’ve done the same, but my number is one more than yours”.

What is Ben’s number?

4 Comments Leave one →

Brian Gladman permalink

Runs in less than 5 milliseconds.


# collect three digit numbers that can be expressed as the sum of
# two or more consecutive integers in exactly two different ways
nrs = {}
for n in range(100, 500):
 
  # express N as the sum of M consecutive integers
  # i.e. in the form M.x + (M - 1).M // 2
  sc, sn, m = 0, [], 2
  while (t := n - (m - 1) * m // 2) > 0 and sc < 3:
    b, r = divmod(t, m)
    if not r:
      sn.append(f"{b}..{b + m - 1}")
      sc += 1
    m += 1
  if sc == 2:
    nrs[n] = sn

# find two consecutive numbers expressed in this way
for m in nrs.keys():
  if m + 1 in nrs.keys():
    print(f"{m} ({' / '.join(nrs[m][::-1])}); {m + 1} "
          f"(Ben's) ({' / '.join(nrs[m + 1][::-1])}).")

# collect three digit numbers that can be expressed as the sum of

# two or more consecutive integers in exactly two different ways

nrs = {}

for n in range(100, 500):

# express N as the sum of M consecutive integers

# i.e. in the form M.x + (M - 1).M // 2

sc, sn, m = 0, [], 2

while (t := n - (m - 1) * m // 2) > 0 and sc < 3:

b, r = divmod(t, m)

if not r:

sn.append(f"{b}..{b + m - 1}")

sc += 1

m += 1

if sc == 2:

nrs[n] = sn

# find two consecutive numbers expressed in this way

for m in nrs.keys():

if m + 1 in nrs.keys():

print(f"{m} ({' / '.join(nrs[m][::-1])}); {m + 1} "

f"(Ben's) ({' / '.join(nrs[m + 1][::-1])}).")

GeoffR permalink


from collections import defaultdict
from itertools import count

d = defaultdict(list)
for n in range(1, 500):
  # sum <cnt> consecutive integers starting with <n> 
  for cnt in count(2):
    csum = cnt * (2 * n + cnt - 1) // 2
    if csum >= 1000:
      break
    # save three digit results
    if csum >= 100:
      d[csum] += [(n, cnt)]

# Find two consecutive numbers that can each be 
# expressed in exactly two ways as consecutive sums
for m in d.keys():
  if m + 1 in d.keys():
    if len(d[m]) == 2 and len(d[m + 1]) == 2:
      print(f"Amelia's number is {m} -> {d[m]}")
      print(f"Ben's number is {m + 1} -> {d[m + 1]}")

from collections import defaultdict

from itertools import count

d = defaultdict(list)

for n in range(1, 500):

# sum <cnt> consecutive integers starting with <n>

for cnt in count(2):

csum = cnt * (2 * n + cnt - 1) // 2

if csum >= 1000:

break

# save three digit results

if csum >= 100:

d[csum] += [(n, cnt)]

# Find two consecutive numbers that can each be

# expressed in exactly two ways as consecutive sums

for m in d.keys():

if m + 1 in d.keys():

if len(d[m]) == 2 and len(d[m + 1]) == 2:

print(f"Amelia's number is {m} -> {d[m]}")

print(f"Ben's number is {m + 1} -> {d[m + 1]}")

Brian Gladman permalink

Here is a solution based on an analysis that leads to a solution based on a the generalised Pell’s equation. This requires the latest version of my Python number_theory library available here.


# Numbers that can be represented as the sums of consecutive integers
#
# This analysis is an extension of John Crabtree's original work.
#
# Let N = 2^k.A.B where A and B are both odd with B > A and k = 0, 1, 2, ...
#
# (1) Let i = (A.B - 1) / 2 and consider the sequence of A.B terms:
#        
#         2^k - i, 2^k - i + 1, ..., 2^k, ..., 2^k + i - 1, 2^k + i
#              
#     These sum to N and are all positive provided that A.B <= 2^(k + 1)
#    
#     Now let i = (A.B + 1) / 2 - 2^k and consider the 2^(k + 1) term sequence:
#        
#         i, i + 1, ..., i + 2^(k + 1) - 1
#        
#     These also sum to N and are all positive provided that A.B >= 2^(k + 1)
#      
#     So this sequence has min(A.B, 2^{k + 1}) terms.
#
# (2) Let i = (A - 1) / 2 and consider the sequence of A terms:
#    
#         2^k.B - i, 2^k.B - i + 1, ..., 2^k.B, ..., 2^k.B + i - 1, 2^k.B + i
#        
#     These have a sum of N and, since 2^k.B > i, they are all positive.
#      
#     This sequence has A terms.
#
# (3) Let i = (B - 1) / 2 and consider the sequence of B terms:
#    
#        2^k.A - i, 2^k.A - i + 1, ..., 2^k.A, ..., 2^k.A + i - 1, 2^k.A + i
#        
#     These sum to N and are all positive provided that B <= 2^(k + 1).A
#       
#     Now let i = (B + 1) / 2 - 2^k.A and consider the 2^(k + 1).A term sequence:
#        
#         i, i + 1, ..., i + 2^(k + 1).A - 1
#        
#     These also sum to N and are all positive provided that B >= 2^(k + 1).A
#      
#     This sequence has min(B, 2^{k + 1}.A) terms. 
#
# So numbers that are the product a power of 2 and two different odd numbers
# will always have more than two representations.
#
# So the only such numbers that could have exactly two representations are 
# the product of a power of 2 and the square of a prime.
#
# Note also that the number of ways that a number N can be written as the sum of M
# consecutive integers (M > 1) is one less than the number of odd divisors of N.
  
# We are looking for two consecutive values each with exactly two representations. 
# Let the odd value be p^2 and the even value be 2^(2.k + 1).r^2 where p and q are 
# both prime. So we have:
#
#    p^2 - 2.(2^k.q)^2 = +/- 1  
#    
# which is a quadratic diophantine equation.

from heapq import merge
from number_theory import is_prime, Qde

# derive the two additive sequences for the value 2^k.p
def seqs(k, p):
  p2, k2 = p * p, 2 ** k
  if p2 <= 2 * k2:
    b1, l1 = k2 - (p2 - 1) // 2, p2
  else:
    b1, l1 = (p2 + 1) // 2 - k2, 2 * k2
        
  b2, l2 = k2 * p - (p - 1) // 2, p
  
  s1 = f"{b1:,}({l1:,})"
  s2 = f"{b2:,}({l2:,})"
  return ' / '.join((s1, s2) if b1 <= b2 else (s2, s1))

cnt = 0
# merge quadratic diophantine solutions for right hand sides of -1 and +1
for p, r in merge(Qde(2, -1).solve(), Qde(2,  1).solve()):
  
  # output the first four solutions 
  if cnt == 4:
    break
  
  # p must be prime 
  if is_prime(p):
    
    # find q and k such that r = 2^k.q with q odd
    q, k = r, 0
    while not q % 2:
      q //= 2
      k += 1
    k = 2 * k + 1
    # q must also be prime
    if is_prime(q):
      
      # find additive sequences for the two solutions
      u = (seqs(0, p), seqs(k, q))

      # output the solutions in right numerical order
      v = (p * p, 2 * r * r)    
      a, b = reversed(v) if v[0] - v[1] == 1 else v
      c, d = reversed(u) if v[0] - v[1] == 1 else u
      print(f"{a:,} / {b:,}\n  {c:}\n  {d}\n")
      cnt += 1

# Numbers that can be represented as the sums of consecutive integers

# This analysis is an extension of John Crabtree's original work.

# Let N = 2^k.A.B where A and B are both odd with B > A and k = 0, 1, 2, ...

# (1) Let i = (A.B - 1) / 2 and consider the sequence of A.B terms:

# 2^k - i, 2^k - i + 1, ..., 2^k, ..., 2^k + i - 1, 2^k + i

# These sum to N and are all positive provided that A.B <= 2^(k + 1)

# Now let i = (A.B + 1) / 2 - 2^k and consider the 2^(k + 1) term sequence:

# i, i + 1, ..., i + 2^(k + 1) - 1

# These also sum to N and are all positive provided that A.B >= 2^(k + 1)

# So this sequence has min(A.B, 2^{k + 1}) terms.

# (2) Let i = (A - 1) / 2 and consider the sequence of A terms:

# 2^k.B - i, 2^k.B - i + 1, ..., 2^k.B, ..., 2^k.B + i - 1, 2^k.B + i

# These have a sum of N and, since 2^k.B > i, they are all positive.

# This sequence has A terms.

# (3) Let i = (B - 1) / 2 and consider the sequence of B terms:

# 2^k.A - i, 2^k.A - i + 1, ..., 2^k.A, ..., 2^k.A + i - 1, 2^k.A + i

# These sum to N and are all positive provided that B <= 2^(k + 1).A

# Now let i = (B + 1) / 2 - 2^k.A and consider the 2^(k + 1).A term sequence:

# i, i + 1, ..., i + 2^(k + 1).A - 1

# These also sum to N and are all positive provided that B >= 2^(k + 1).A

# This sequence has min(B, 2^{k + 1}.A) terms.

# So numbers that are the product a power of 2 and two different odd numbers

# will always have more than two representations.

# So the only such numbers that could have exactly two representations are

# the product of a power of 2 and the square of a prime.

# Note also that the number of ways that a number N can be written as the sum of M

# consecutive integers (M > 1) is one less than the number of odd divisors of N.

# We are looking for two consecutive values each with exactly two representations.

# Let the odd value be p^2 and the even value be 2^(2.k + 1).r^2 where p and q are

# both prime. So we have:

# p^2 - 2.(2^k.q)^2 = +/- 1

# which is a quadratic diophantine equation.

from heapq import merge

from number_theory import is_prime, Qde

# derive the two additive sequences for the value 2^k.p

def seqs(k, p):

p2, k2 = p * p, 2 ** k

if p2 <= 2 * k2:

b1, l1 = k2 - (p2 - 1) // 2, p2

else:

b1, l1 = (p2 + 1) // 2 - k2, 2 * k2

b2, l2 = k2 * p - (p - 1) // 2, p

s1 = f"{b1:,}({l1:,})"

s2 = f"{b2:,}({l2:,})"

return ' / '.join((s1, s2) if b1 <= b2 else (s2, s1))

cnt = 0

# merge quadratic diophantine solutions for right hand sides of -1 and +1

for p, r in merge(Qde(2, -1).solve(), Qde(2, 1).solve()):

# output the first four solutions

# find q and k such that r = 2^k.q with q odd

# q must also be prime

if is_prime(q):

# find additive sequences for the two solutions

u = (seqs(0, p), seqs(k, q))

# output the solutions in right numerical order

v = (p * p, 2 * r * r)

a, b = reversed(v) if v[0] - v[1] == 1 else v

c, d = reversed(u) if v[0] - v[1] == 1 else u

print(f"{a:,} / {b:,}\n {c:}\n {d}\n")

cnt += 1

John Zalewski permalink


# whole number a = n+1 + n+2 + n+3 ... + n+j if it is the sum of j consecutive
# numbers so   a = n*j + j*(j+1)/2
#              a - j*(j+1)/2 = n * j
#              (a - j*(j+1)/2)/j = n
#
# this is true for any a and any j if (a-(j*(j+1)/2))%j==0 and a >= j*(j+1)/2
#i.e. (a-(j*(j+1)/2))/j=n with n integer 

aprev = 0
for a in range(99, 999):
  tot = 0
  for j in range (2, 45): # 990 = 1 + 2 + 3 ... + 44  
    tot += a >= j * (j + 1) / 2 and (a - (j * (j + 1) / 2)) % j == 0 

  if tot == 2:
    if aprev + 1 == a: 
      print ("Ben's number", a," Amelia's number", aprev)
    aprev = a

# whole number a = n+1 + n+2 + n+3 ... + n+j if it is the sum of j consecutive

# numbers so a = n*j + j*(j+1)/2

# a - j*(j+1)/2 = n * j

# (a - j*(j+1)/2)/j = n

# this is true for any a and any j if (a-(j*(j+1)/2))%j==0 and a >= j*(j+1)/2

#i.e. (a-(j*(j+1)/2))/j=n with n integer

aprev = 0

for a in range(99, 999):

tot = 0

for j in range (2, 45): # 990 = 1 + 2 + 3 ... + 44

tot += a >= j * (j + 1) / 2 and (a - (j * (j + 1) / 2)) % j == 0

if tot == 2:

if aprev + 1 == a:

print ("Ben's number", a," Amelia's number", aprev)

aprev = a

Sunday Times Teaser 2994 – Consecutive Sums

by Bill Kinally

Published Sunday February 09 2020 (link)

Leave a comment to GeoffR Cancel reply

Recent Posts

Recent Comments

Archives

Categories

Meta