The houses puzzle

README.md

Problem

A certain street has between 50 and 500 houses in a row, numbered 1, 2, 3, 4, … consecutively. There is a certain house on the street such that the sum of all the house numbers to the left side of it is equal to the sum of all the house numbers to its right. Find the number of this house.

— source

Solution

If there are k houses and we are at house n, we can relate k and n using the triangular numbers as follows:

(n-1)n/2 = k(k+1)/2 - n(n+1)/2
...
1 = (2k+1)^2 - 8n^2

This can be re-written as the following Pell equation:

1 = K^2 - 8N^2

Integer pairs (K, N) can thus be found by partially evaluating the continued fraction of sqrt(8).

This gist contains Factor code to do so.

IN: scratchpad 10 houses .
{
    { 1 1 }
    { 8 6 }
    { 49 35 }
    { 288 204 }
    { 1681 1189 }
    { 9800 6930 }
    { 57121 40391 }
    { 332928 235416 }
    { 1940449 1372105 }
    { 11309768 7997214 }
}
IN: scratchpad : triangle ( n -- n ) dup 1 + * 2/ ;
IN: scratchpad 11309768 triangle 7997214 triangle - 7997213 triangle = .
t

continued-fractions-tests.factor

! Copyright (C) 2020 Jordan Scales.
! See http://factorcode.org/license.txt for BSD license.
USING: tools.test math continued-fractions ;
IN: continued-fractions.tests

{ 3 } [ { 3 } eval ] unit-test
{ 4+3/10 } [ { 1 2 3 4 } eval ] unit-test

{ { 3 } } [ 1 8frac ] unit-test
{ { -6 3 } } [ 2 8frac ] unit-test
{ { 6 -6 6 -6 6 -6 6 -6 3 } } [ 9 8frac ] unit-test
{ { } } [ 0 8frac ] unit-test

{ { { 3 1 } } } [ 1 8pell ] unit-test
{ { { 3 1 } { 17 6 } } } [ 2 8pell ] unit-test
{ { { 3 1 }
    { 17 6 }
    { 99 35 }
    { 577 204 }
} } [ 4 8pell ] unit-test

{ { { 1 1 }
    { 8 6 }
    { 49 35 }
    { 288 204 }
    { 1681 1189 }
    { 9800 6930 }
    { 57121 40391 }
    { 332928 235416 }
    { 1940449 1372105 }
    { 11309768 7997214 }
} } [ 10 houses ] unit-test

continued-fractions.factor

! Copyright (C) 2020 Jordan Scales.
! See http://factorcode.org/license.txt for BSD license.
USING: kernel math sequences arrays ;
IN: continued-fractions

: eval ( arr -- float )
  [ 0 swap remove-nth ]
  [ 0 swap nth ]
  bi                  ! { a b c ... } -- { b c ... } a
  [ [ recip ] dip + ] ! a b -- (1/a + b)
  reduce ;

: 8frac ( n -- arr )
  [ 0 > [ { 3 } ] [ { } ] if ] keep
  dup 0 >
      ! generate a string of n-1 6's and -6
      ! alternating, starting with -6
      [ 6 swap 1 - [ -1 * dup ] replicate nip ]
      [ { } nip ]
      if
  append
  reverse ;

! the first `count` integer pairs (K, N) s.t. 1 = K^2 - 8N^2
: 8pell ( count -- arr )
  0 swap [ 1 + dup ] replicate nip  ! [1..count]
  [ 8frac eval [ numerator ] [ denominator ] bi 2array ]
  map ;

! Produce the first `count` pairs (k, n), such that there
! are k houses numbered 1 to k, you are at house n, and
! the sum of the house numbers to your left is equal to the
! sum of the house numbers to your right.
!
! EXPLANATION:
!   Using the triangle numbers, we can relate k and n:
!     1 = (2k+1)^2 - 8n^2
!   This can be represented as the Pell equation
!     1 = K^2 - 8N^2
!   Where integer (K, N) pairs can be generated by partially
!   evaluating the continued fraction of sqrt(8).
: houses ( count -- arr )
  8pell
  [
    [ 0 swap nth -1 + 2/ ]
    [ 1 swap nth ]
    bi
    2array
  ] map ;