The challenge

The drawing shows 6 squares the sides of which have a length of 1, 1, 2, 3, 5, 8. It’s easy to see that the sum of the perimeters of these squares is : 4 * (1 + 1 + 2 + 3 + 5 + 8) = 4 * 20 = 80

Could you give the sum of the perimeters of all the squares in a rectangle when there are n + 1 squares disposed in the same manner as in the drawing:

Hint: See Fibonacci sequence

Ref:

http://oeis.org/A000045

The function perimeter has for parameter n where n + 1 is the number of squares (they are numbered from 0 to n) and returns the total perimeter of all the squares.

1
2

perimeter(5)  should return 80
perimeter(7)  should return 216

The solution in Java code

Option 1:

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20

import java.math.BigInteger;

public class SumFct {
  public static BigInteger perimeter(BigInteger n) {
    
    BigInteger a = BigInteger.ZERO;
    BigInteger b = BigInteger.ONE;
    BigInteger c = BigInteger.ONE;
    BigInteger sum = BigInteger.ZERO;
     
    for(int i = 0; i <= n.intValue(); i++) {
      a = b;
      b = c;
      c = a.add(b);
      sum = sum.add(a);      
    }
    
    return sum.multiply(BigInteger.valueOf(4));
  }
}

Option 2:

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20

import java.math.BigInteger;

public class SumFct {
  public static BigInteger perimeter(BigInteger n) {
    
    BigInteger a = BigInteger.ZERO;
    BigInteger b = BigInteger.ONE;
    BigInteger c = BigInteger.ONE;
    BigInteger sum = BigInteger.ZERO;
     
    for(int i = 0; i <= n.intValue(); i++) {
      a = b;
      b = c;
      c = a.add(b);
      sum = sum.add(a);      
    }
    
    return sum.multiply(BigInteger.valueOf(4));
  }
}

Option 3:

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15

import java.math.BigInteger;
public class SumFct {
  public static BigInteger perimeter(BigInteger n) {
    BigInteger fibSum = BigInteger.ONE;
    BigInteger previousFibValue = BigInteger.ZERO;
    BigInteger currentFibValue = BigInteger.ONE;
    
    for (BigInteger i = BigInteger.ONE; i.compareTo(n) < 1; i = i.add(BigInteger.ONE)) {
      currentFibValue = currentFibValue.add(previousFibValue);
      previousFibValue = currentFibValue.subtract(previousFibValue);
      fibSum = fibSum.add(currentFibValue);
    }
    return fibSum.multiply(BigInteger.valueOf(4));
  }
}

Test cases to validate our solution

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74

import static org.junit.Assert.*;
import java.math.BigInteger;
import java.util.HashMap;
import java.util.Random;
import org.junit.Test;


public class SumFctTest {
  private static HashMap<BigInteger, BigInteger> cache = new HashMap<BigInteger, BigInteger>();
    private static BigInteger ONE  = BigInteger.ONE;
    private static BigInteger ZERO = BigInteger.ZERO;

  public static BigInteger fib(BigInteger n) {
        if (n.equals(ZERO)) return ZERO;
        if (n.equals(ONE))  return ONE;
        if (cache.containsKey(n)) return cache.get(n);

        // odd
        if (n.testBit(0)) {
            BigInteger n2 = n.shiftRight(1);
            BigInteger n3 = n2.add(ONE);
            BigInteger result = fib(n2).multiply(fib(n2)).add(fib(n3).multiply(fib(n3)));
            cache.put(n, result);
            return result;
        }
        // even
        else {
            BigInteger n2 = n.shiftRight(1);
            BigInteger n3 = n2.subtract(ONE);
            BigInteger result = fib(n2).multiply(fib(n2).add(fib(n3).add(fib(n3))));
            cache.put(n, result);
            return result;
        }
    }
  
  public static BigInteger solution(BigInteger n) {
    return (fib(n.add(BigInteger.valueOf(3))).subtract(BigInteger.valueOf(1))).multiply(BigInteger.valueOf(4));
  }

  @Test
  public void test1() {
    assertEquals(BigInteger.valueOf(80), SumFct.perimeter(BigInteger.valueOf(5)));
  }
  @Test
  public void test2() {
    assertEquals(BigInteger.valueOf(216), SumFct.perimeter(BigInteger.valueOf(7)));
  }
  @Test
  public void test3() {
    assertEquals(BigInteger.valueOf(14098308), SumFct.perimeter(BigInteger.valueOf(30)));
  }
  @Test
  public void test4() {
    BigInteger r = new BigInteger("6002082144827584333104");
    assertEquals(r, SumFct.perimeter(BigInteger.valueOf(100)));
  }
  @Test
  public void test5() {
    BigInteger r = new BigInteger("2362425027542282167538999091770205712168371625660854753765546783141099308400948230006358531927265833165504");
    assertEquals(r, SumFct.perimeter(BigInteger.valueOf(500)));
  }
  
  @Test
  public void test6() {
    System.out.println("****** Random test ******");
    Random rnd = new Random();
    for (int i = 0; i < 25; i++) {    
      int a = Math.round(rnd.nextInt(1000) * (65 - 10) + 10000);
            System.out.println("Perimeter for : " + a);
            assertEquals(SumFctTest.solution(BigInteger.valueOf(a)), SumFct.perimeter(BigInteger.valueOf(a)));
    }
  }

}