You are currently browsing the tag archive for the ‘coding’ tag.

Waging war with maths: Hollow squares

The picture above [US National Archives, Wikipedia] shows an example of the hollow square infantry formation which was used in wars over several hundred years.  The idea was to have an outer square of men, with an inner empty square.  This then allowed the men in the formation to be tightly packed, facing the enemy in all 4 directions, whilst the hollow centre allowed the men flexibility to rotate (and also was a place to hold supplies).  It was one of the infantry formations of choice against charging cavalry.

So, the question is, what groupings of men can be arranged into a hollow square?  This is a current Nrich investigation, so I thought I’d do a mini-investigation on this.

We can rethink this question as asking which numbers can be written as the difference between 2 squares. For example in the following diagram (from the Nrich task Hollow Squares)

We can see that the hollow square formation contains a larger square of 20 by 20 and a smaller hollow square of 8 by 8.  Therefore the number of men in this formation is:

202-82 = 336.

The first question we might ask therefore is how many numbers from 1-100 can be written as the difference between 2 squares?  These will all be potential formations for our army.

I wrote a quick code on Python to find all these combinations.  I included 0 as a square number (though this no longer creates a hollow square, rather just a square!). You can copy this and run it in a Python editor like Repl.it.


for k in range(1,50):

  for a in range(0, 100):
   for b in range(0,100):
    if a**2-b**2 == k :
     print(k,a,b)

This returned the following results:

1 1 0
3 2 1
4 2 0
5 3 2
7 4 3
8 3 1
9 3 0
9 5 4
11 6 5
12 4 2
13 7 6
15 4 1
15 8 7
16 4 0
16 5 3
17 9 8
19 10 9
20 6 4
21 5 2
21 11 10
23 12 11
24 5 1
24 7 5
25 5 0
25 13 12
27 6 3
27 14 13
28 8 6
29 15 14
31 16 15
32 6 2
32 9 7
33 7 4
33 17 16
35 6 1
35 18 17
36 6 0
36 10 8
37 19 18
39 8 5
39 20 19
40 7 3
40 11 9
41 21 20
43 22 21
44 12 10
45 7 2
45 9 6
45 23 22
47 24 23
48 7 1
48 8 4
48 13 11
49 7 0
49 25 24

Therefore we can see that the numbers with no solutions found are:

2,6,10,14,18,22,26,30,34,38,42,46,50

which are all clearly in the sequence 4n-2.

Thinking about this, we can see that this can be written as 2(2n-1) which is the product of an even number and an odd number. This means that all numbers in this sequence will require an odd factor in each of their factor pairs:

eg. 50 can be written as 10 (even) x 5 (odd) or 2 (even) x 25 (odd) etc.

But with a2-b2 = (a+b)(a-b), due to symmetries we will always end up with (a+b) and (a-b) being both even or both odd, so we can’t create a number with a factor pair of one odd and one even number. Therefore numbers in the sequence 4n-2 can’t be formed as the difference of 2 squares. There are some nicer (more formal) proofs of this here.

A battalion with 960 soldiers

Next we are asked to find how many different ways of arranging 960 soldiers in a hollow square. So let’s modify the code first:


for a in range(0, 1000):
 for b in range(0,1000):
  if a**2-b**2 == 960 :
   print(a,b)

Which gives us the following solutions:

31 1
32 8
34 14
38 22
46 34
53 43
64 56
83 77
122 118
241 239

General patterns

We can notice that when the number of soldiers is 1,3,5,7,9,11 (2n-1) we can always find a solution with the pair n and n-1. For example, 21 can be written as 2n-1 with n = 11. Therefore we have 10 and 11 as our pair of squares. This works because 112-102 = (11+10)(11-10) returns the factor pair 21 and 1. In general it always returns the factor pair, 2n-1 and 1.

We can also notice that when the number of soldiers is 4,8,12,16,20 (4n) we can always find a solution with the pair n+1 and n-1. For example, 20 can be written as 4n with n = 5. Therefore we have 6 and 4 as our pair of squares. This works because 62-42 = (6+4)(6-4) returns the factor pair 10 and 2. In general it always returns the factor pair, 2n and 2.

And we have already shown that numbers 2,6,10,14,18,22 (4n-2) will have no solution. These 3 sequences account for all the natural numbers (as 2n-1 incorporates the 2 sequences 4n-3 and 4n-1).

So, we have found a method of always finding a hollow square formation (if one exists) as well as being able to use some computer code to find other possible solutions. There are lots of other avenues to explore here – could you find a method for finding all possible combinations for a given number of men? What happens when the hollow squares become rectangles?

Screen Shot 2019-05-27 at 9.06.57 AM

Computers can brute force a lot of simple mathematical problems, so I thought I’d try and write some code to solve some of them.  In nearly all these cases there’s probably a more elegant way of coding the problem – but these all do the job!  You can run all of these with a Python editor such as Repl.it.  Just copy and paste the below code and see what happens.

1) Happy Numbers.

Happy numbers are defined by the rule that you start with any positive integer, square each of the digits then add them together. Now do the same with the new number. Happy numbers will eventually spiral down to a number of 1. Numbers that don’t eventually reach 1 are called unhappy numbers.

As an example, say we start with the number 23. Next we do 2²+3² = 13. Now, 1²+3² = 10. Now 1²+0² = 1. 23 is therefore a happy number.


k= int(input("type a 2 digit number "))
a = int(k%10)
c = int(k//100)
b = int(k//10 -10*c)
print (a**2+b**2+c**2)

for k in range (1,20):

  k = a**2+b**2 + c**2
  a = int(k%10)
  c = int(k//100)
  b = int(k//10 -10*c)
  print (a**2+b**2+c**2)

2) Sum of 3 cubes

Most (though not all) numbers can be written as the sum of 3 cubes. For example:
13 + 23 + 23 = 17. Therefore 17 can be written as the sum of 3 cubes.

This program allows you to see all the combinations possible when using the integers -10 to 10 and trying to make all the numbers up to 29.


for k in range(1,30):

  for a in range(-10, 10):
    for b in range(-10,10):
      for c in range (-10, 10):
        if a**3+b**3+c**3 == k :
          print(k,a,b,c)

3) Narcissistic Numbers

A 3 digit narcissistic number is defined as one which the sum of the cubes of its digits equal the original number. This program allows you to see all 3 digit narcissistic numbers.

for a in range (0,10):
 for b in range(0, 10):
  for c in range(0,10):
   if a**3 + b**3 + c**3 ==100*a + 10*b + c:
    print(int(100*a + 10*b + c))

4) Pythagorean triples

Pythagorean triples are integer solutions to Pythagoras’ Theorem. For example:
32 + 42 = 52 is an integer solution to Pythagoras’ Theorem.
This code allows you to find all integer solutions to Pythagoras’ Theorem for the numbers in the range you specify.

k = 100

for a in range(1, k):
 for b in range(1,k):
  for c in range (1, 2*k):
   if a**2+b**2==c**2:
    print(a,b,c)

5) Perfect Numbers

Perfect numbers are numbers whose proper factors (factors excluding the number itself) add to the number. This is easier to see with an example.

6 is a perfect number because its proper factors are 1,2,3 and 1+2+3 = 6

8 is not a perfect number because its proper factors are 1,2,4 and 1+2+4 = 7

Perfect numbers have been known about for about 2000 years – however they are exceptionally rare. The first 4 perfect numbers are 6, 28, 496, 8128. These were all known to the Greeks. The next perfect number wasn’t discovered until around 1500 years later – and not surprisingly as it’s 33,550,336.

The code below will find all the perfect numbers less than 10,000.

for n in range(1,10000):
 list = []

 for i in range (1,n):

  if n%i ==0:
   list.append(i)
 if sum(list)==n:
  print(n)

Friendly Numbers

Friendly numbers are numbers which share a relationship with other numbers. They require the use of σ(a) which is called the divisor function and means the addition of all the factors of a. For example σ(7) = 1 + 7 = 8 and σ(10) = 1 +2 +5 + 10 = 18.

Friendly numbers therefore satisfy:

σ(a)/a = σ(b)/b

As an example:

σ(6) / 6 = (1+2+3+6) / 6 = 2,

σ(28) / 28 = (1+2+4+7+14+28) / 28 = 2

σ(496)/496 = (1+2+4+8+16+31+62+124+248+496)/496 = 2

Therefore 28 and 6 are friendly numbers because they share a common relationship.

This code will help find some Friendly numbers (though these are very difficult to find, as we need to check against every other integer until we find a relationship).

The code below will find some Friendly numbers less than 200, and their friendly pair less than 5000:


for n in range(1,5000):
 list = []

 for i in range (1,n+1):
  if n%i ==0:
   list.append(i)
 Result1 = sum(list)
 for m in range(1,200):
  list2 = []
  for j in range (1,m+1):
   if m%j ==0:
    list2.append(j)
  Result2 = sum(list2)

  if Result2/m ==Result1/n:
   if n != m:
    print(n,m)

Hailstone numbers

Hailstone numbers are created by the following rules:

if n is even: divide by 2

if n is odd: times by 3 and add 1

We can then generate a sequence from any starting number. For example, starting with 10:

10, 5, 16, 8, 4, 2, 1, 4, 2, 1…

we can see that this sequence loops into an infinitely repeating 4,2,1 sequence. Trying another number, say 58:

58, 29, 88, 44, 22, 11, 34, 17, 52, 26, 13, 40, 20, 10, 5, 16, 8, 4, 2, 1, 4, 2, 1…

and we see the same loop of 4,2,1.

The question is, does every number end in this loop? Well, we don’t know. Every number mathematicians have checked do indeed lead to this loop, but that is not a proof. Perhaps there is a counter-example, we just haven’t found it yet.

Run the code below, and by changing the value of n you can see how quickly the number enters the 4,2,1 loop.


n = 300
for k in range(1,40):

 if n%2 ==0:
  print(n/2)
  n =n/2
 elif n%2 !=0:
  print(3*n+1)
  n =3*n+1

Generating the Golden ratio

The Golden ratio can be approximated by dividing any 2 successive terms of the Fibonacci sequence. As we divide ever larger successive terms we get a better approximation for the Golden ratio. This code returns successive terms of the Fibonacci sequence and the corresponding approximation for the Golden ratio.


a = 0
b = 1
print(a)
print(b)
for k in range(1,30):

 a = a+b
 b = a+b

 print(a,b, b/a)

Partial sums

We can use programs to see if sums to infinity converge. For example with the sequence 1/n, if I add the terms together I get: 1/1 + 1/2 + 1/3 + 1/4…In this case the series (surprisingly) diverges. The code below shows that the sum of the sequence 1/n2 converges to a number (pi2/6).

list = []
for n in range(1,100):
 n = 1/(n**2)
 list.append(n)
 print(sum(list))

Returning to 6174

This is a nice number trick. You take any 4 digit number, then rearrange the digits so that you make the largest number possible and also the smallest number possible. You then take away the smallest number from the largest number, and then start again. For example with the number 6785, the largest number we can make is 8765 and the smallest is 5678. So we do 8765 – 5678 = 3087. We then carry on with the same method. Eventually we will arrive at the number 6174!


k= int(input("type a 4 digit number "))
a = int(k%10)
d = int(k//1000)
c = int(k//100 - 10*d)
b = int(k//10 -10*c-100*d)

for n in range(1,10):

 list = []
 list = [a,b,c,d]
 list.sort()

 a = list[0]
 d = list[3]
 c = list[2]
 b = list[1]
 print(1000*d+100*c+10*b+a -1000*a-100*b-10*c-d)
 k = int(1000*d+100*c+10*b+a -1000*a-100*b-10*c-d)
 a = int(k%10)
 d = int(k//1000)
 c = int(k//100 - 10*d)
 b = int(k//10 -10*c-100*d)
 list = []
 list = [a,b,c,d]
 list.sort()

 a = list[0]
 d = list[3]
 c = list[2]
 b = list[1]

 print(1000*d+100*c+10*b+a -1000*a-100*b-10*c-d)

Maximising the volume of a cuboid

If we take a cuboid of length n, and cut squares of size x from the corner, what value of x will give the maximum volume? This code will look at initial squares of size 10×10 up to 90×90 and find the value of x for each which give the maximum volume.


def compute():

 list1=[]
 k=6
 z = int(0.5*a*10**k)

 for x in range(1,z):
  list1.append((10*a-2*x/10**(k-1))*(10*a-2*x/10**(k-1))*(x/10**(k-1)))
 print("length of original side is, ", 10*a)
 y= max(list1)
 print("maximum volume is, ", max(list1))

 q = list1.index(y)
 print("length of square removed from corner is, ", (q+1)/10**(k-1))

for a in range(1,10):
 print(compute())

Stacking cannonballs – solving maths with code

Numberphile have recently done a video looking at the maths behind stacking cannonballs – so in this post I’ll look at the code needed to solve this problem.

Triangular based pyramid.

Screen Shot 2019-05-19 at 3.36.23 PM

A triangular based pyramid would have:

1 ball on the top layer

1 + 3 balls on the second layer

1 + 3 + 6 balls on the third layer

1 + 3 + 6 + 10 balls on the fourth layer.

Therefore a triangular based pyramid is based on the sum of the first n triangular numbers.

The formula for the triangular numbers is:

Screen Shot 2019-05-19 at 3.40.12 PM

and the formula for the sum of the first n triangular numbers is:

Screen Shot 2019-05-19 at 3.40.16 PM

Screen Shot 2019-05-19 at 3.54.28 PM

We can simplify this by using the identity for the sum of the first n square numbers and also the identity for the sum of the first n natural numbers:

Screen Shot 2019-05-19 at 3.54.39 PM

Screen Shot 2019-05-19 at 3.54.35 PM

Therefore:

Screen Shot 2019-05-19 at 3.54.44 PM

and the question we want to find out is whether there is triangular based pyramid with a certain number of cannonballs which can be rearranged into a triangular number i.e.:

Screen Shot 2019-05-19 at 3.54.49 PM

here n and m can be any natural number. For example if we choose n = 3 and m = 4 we see that we have the following:

Screen Shot 2019-05-19 at 3.54.52 PM

Therefore we can have a triangular pyramid of height 3, which has 10 cannonballs. There 10 cannonballs can then be rearranged into a triangular number.

Square based pyramids and above.

Screen Shot 2019-05-19 at 3.36.06 PM

For a square based pyramid we would have:

1 ball on the top layer

1 + 4 balls on the second layer

1 + 4 + 9 balls on the third layer

1 + 4 + 9 + 16 balls on the fourth layer.

This is the sum of the first n square numbers.  So the formula for the square numbers is:

Screen Shot 2019-05-19 at 4.07.43 PM

and the sum of the first n square numbers is:

Screen Shot 2019-05-19 at 4.07.45 PM

For a pentagonal based pyramid we have:

1 ball on the top layer

1 + 5 balls on the second layer

1 + 5 + 12 balls on the third layer

1 + 5 + 12 + 22 balls on the fourth layer.

This is the sum of the first n pentagonal numbers. So the formula for the pentagonal numbers is:

Screen Shot 2019-05-19 at 4.07.48 PM

and the formula for the first n pentagonal numbers is:

Screen Shot 2019-05-19 at 4.07.51 PM

For a hexagonal based pyramid we have:

The formula for the first n hexagonal numbers:

Screen Shot 2019-05-19 at 4.07.55 PM

and the formula for the sum of the first n hexagonal numbers:

Screen Shot 2019-05-19 at 4.07.58 PM

For a k-agon based pyramid we have

Screen Shot 2019-05-19 at 4.08.01 PM

and the formula for the sum of the first n k-agon numbers:

Screen Shot 2019-05-19 at 4.20.16 PM

Screen Shot 2019-05-19 at 4.20.22 PM

Screen Shot 2019-05-19 at 4.20.25 PM

Therefore the general case is to ask if a k-agonal pyramid can be rearranged into a k-agon number i.e:

Screen Shot 2019-05-19 at 4.20.29 PM

Computers to the rescue

We can then use some coding to brute force some solutions by running through large numbers of integers and seeing if any values give a solution.  Here is the Python code.  Type it (taking care with the spacing) into a Python editor and you can run it yourself.

Screen Shot 2019-05-19 at 4.28.45 PM

You can then change the k range to check larger k-agons and also change the range for a and b.  Running this we can find the following.  (The first number is the value of k, the second the height of a k-agonal pyramid, the third number the k-agon number and the last number the number of cannonballs used).

Solutions:

3 , 3 , 4 , 10
3 , 8 , 15 , 120
3 , 20 , 55 , 1540
3 , 34 , 119 , 7140
4 , 24 , 70 , 4900
6 , 11 , 22 , 946
8 , 10 , 19 , 1045
8 , 18 , 45 , 5985
10 , 5 , 7 , 175
11 , 25 , 73 , 23725
14 , 6 , 9 , 441
14 , 46 , 181 , 195661
17 , 73 , 361 , 975061
20 , 106 , 631 , 3578401
23 , 145 , 1009 , 10680265
26 , 190 , 1513 , 27453385
29 , 241 , 2161 , 63016921
30 , 17 , 41 , 23001
32 , 298 , 2971 , 132361021
35 , 361 , 3961 , 258815701
38 , 430 , 5149 , 477132085
41 , 204 , 1683 , 55202400
41 , 505 , 6553 , 837244045
43 , 33 , 110 , 245905
44 , 586 , 8191 , 1408778281
50 , 34 , 115 , 314755
88 , 15 , 34 , 48280
145, 162, 1191, 101337426
276,  26,  77, 801801)
322, 28, 86, 1169686
823, 113, 694, 197427385
2378, 103, 604, 432684460
31265, 259, 2407,  90525801730

Screen Shot 2019-05-19 at 8.58.44 PM

For example we can see a graphical representation of this.  When k is 6, we have a hexagonal pyramid with height 11 or the 22nd hexagonal number – both of which give a solution of 946.  These are all the solutions I can find – can you find any others?  Leave a comment below if you do find any others and I’ll add them to the list!

What’s so special about 277777788888899?

Numberphile have just done a nice video which combines mathematics and computer programing.  The challenge is to choose any number (say 347)

Then we do 3x4x7 = 84

next we do 8×4 = 32

next we do 3×2 = 6.

And when we get to a single digit number then we have finished.  It took 3 steps to get from 347 to a single digit number, therefore 347 has a persistence of 3.  The challenge is to find a number with as big a persistence as possible.  The current world record is 277777788888899 which is the smallest number with a persistence of 11.  No numbers with a persistence of greater than 11 have ever been found.  In the video Matt writes a Python program to check this, though I tried to make my own version below.  It’s not very sophisticated, but it gets the job done (with a small glitch of returning a 0 followed by 1s when it should just return 0s!)

Screen Shot 2019-04-08 at 9.37.27 AM
The full code should be available to run here, or download here. If you run the program above in an online Python site like repl.it you can choose any number you like as see what its persistence is.

Screen Shot 2019-04-08 at 9.16.46 AM

 

If you find any number that hasn’t gone to a single digit after 11 rounds, you’ve found a new world record persistence!

To very briefly explain the code used above:

Screen Shot 2019-04-08 at 9.39.38 AM

We start by defining “result” as 1.  We then have some add any integer number on the screen (let’s use 347).  We then do 347 mod 10 (number % 10) which gives 7, and do result (which is 1) multiplied by 7.  We then do 347 divided by 10 ignoring remainders (number//10).  This gives 34.

We then start the process again. 34 mod 10 = 4.  So now we have 1 x 7 x 4.  Next we do 34 divided by 10 ignoring remainders which gives 3.  Last we do 3 mod 10 = 3. So we have 1 x 7 x 4 x 3.  If we carried on the loop we would next have 3/10 = 0 ignoring remainders, therefore our loop would stop.

The program then defines the new starting number as 7x4x3 = 84 and then starts again. So, a nice use of mathematics and computing – see what levels of persistence you can find!

Project Euler: Coding to Solve Maths Problems

Project Euler, named after one of the greatest mathematicians of all time, has been designed to bring together the twin disciplines of mathematics and coding.  Computers are now become ever more integral in the field of mathematics – and now creative coding can be a method of solving mathematics problems just as much as creative mathematics has always been.

The first problem on the Project Euler Page is as follows:

If we list all the natural numbers below 10 that are multiples of 3 or 5, we get 3, 5, 6 and 9. The sum of these multiples is 23.

Find the sum of all the multiples of 3 or 5 below 1000.

This is a reasonably straight forward maths problem which we can solve using the summation of arithmetic sequences (I’ll solve it below!) but more interestingly is how a computer code can be written to solve this same problem.  Given that I am something of a coding novice, I went to the Project Nayuki website which has an archive of solutions.  Here is a slightly modified version of the solution given on Project Nayki, designed to run in JAVA:

 

The original file can be copied from here, I then pasted this into an online JAVA site jdoodle. The only modification necessary was to replace:

public final class p001 implements EulerSolution with public class p001

Then after hitting execute you get the following result:

i.e the solution is returned as 233,168. Amazing!

But before we get carried away, let’s check the answer using some more old fashioned maths. We can break down the question into simply trying to find the sum of multiples of 3 under 1000, the sum of the multiples of 5 under 1000 and then subtracting the multiples of 15 under 1000 (as these will have been double counted). i.e:

(3 + 6 + 9 + … 999)  +  (5 + 10 + 15 + … 995)  – (15 + 30 + 45 + …990)

This gives:

S_333 = 333/2 (2(3)+ 332(3)) = 166,833
+
S_199 = 199/2 (2(5) + 198(5)) = 99, 500

S_66 = 66/2 (2(15) +65(15) = 33, 165.

166,833 + 99, 500 – 33, 165 = 233, 168 as required.

Now that we have seen that this works we can modify the original code.  For example if we replace:

if (i % 3 == 0 || i % 3 == 0)
with
if (i % 5 == 0 || i % 7 == 0)

This will find the sum of all the multiples of 5 or 7 below 1000.  Which returns the answer 156,361.

Replacing the same line with:

if (i % 5 == 0 || i % 7 == 0 || i % 3 == 0)

will find the sum of all the multiples of 3 or 5 or 7 below 1000, which returns the answer 271,066.  To find this using the previous method we would have to do:

Sum of 3s + Sum of 5s – Sum of 15s + Sum of 7s – Sum of 21s – Sum 35s – Sum of 105s. Which starts to show why using a computer makes life easier.

This would be a nice addition to any investigation on Number Theory – or indeed a good project for anyone interested in Computer Science as a possible future career.

Website Stats

  • 6,593,838 views

Recent Posts

Follow IB Maths Resources from British International School Phuket on WordPress.com