## 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:

#### Ref:

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 cache = new HashMap(); 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))); } } } ``````