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

**Sierpinski Triangle: A picture of infinity**

This pattern of a Sierpinski triangle pictured above was generated by a simple iterative program. I made it by modifying the code previously used to plot the Barnsley Fern. You can run the code I used on repl.it. What we are seeing is the result of 30,000 iterations of a simple algorithm. The algorithm is as follows:

**Transformation 1:**

x_{i+1} = 0.5x_{i}

y_{i+1}= 0.5y_{i}

**Transformation 2:**

x_{i+1} = 0.5x_{i} + 0.5

y_{i+1}= 0.5y_{i}+0.5

**Transformation 3:**

x_{i+1} = 0.5x_{i} +1

y_{i+1}= 0.5y_{i}

So, I start with (0,0) and then use a random number generator to decide which transformation to use. I can run a generator from 1-3 and assign 1 for transformation 1, 2 for transformation 2, and 3 for transformation 3. Say I generate the number 2 – therefore I will apply transformation 2.

x_{i+1} = 0.5(0) + 0.5

y_{i+1}= 0.5(0)+0.5

and my new coordinate is (0.5,0.5). I mark this on my graph.

I then repeat this process – say this time I generate the number 3. This tells me to do transformation 3. So:

x_{i+1} = 0.5(0.5) +1

y_{i+1}= 0.5(0.5)

and my new coordinate is (1.25, 0.25). I mark this on my graph and carry on again. The graph above was generated with 30,000 iterations.

**Altering the algorithm**

We can alter the algorithm so that we replace all the 0.5 coefficients of x and y with another number, *a*.

a = 0.3 has disconnected triangles:

When a = 0.7 we still have a triangle:

By a = 0.9 the triangle is starting to degenerate

By a = 0.99 we start to see the emergence of a line “tail”

By a = 0.999 we see the line dominate.

And when a = 1 we then get a straight line:

When a is greater than 1 the coordinates quickly become extremely large and so the scale required to plot points means the disconnected points are not visible.

If I alternatively alter transformations 2 and 3 so that I add b for transformation 2 and 2b for transformation 3 (rather than 0.5 and 1 respectively) then we can see we simply change the scale of the triangle.

When b = 10 we can see the triangle width is now 40 (we changed b from 0.5 to 10 and so made the triangle 20 times bigger in length):

**Fractal mathematics**

This triangle is an example of a self-similar pattern – i.e one which will look the same at different scales. You could zoom into a detailed picture and see the same patterns repeating. Amazingly fractal patterns don’t fit into our usual understanding of 1 dimensional, 2 dimensional, 3 dimensional space. Fractals can instead be thought of as having fractional dimensions.

The Hausdorff dimension is a measure of the “roughness” or “crinkley-ness” of a fractal. It’s given by the formula:

D = log(N)/log(S)

For the Sierpinski triangle, doubling the size (i.e S = 2), creates 3 copies of itself (i.e N =3)

This gives:

D = log(3)/log(2)

Which gives a fractal dimension of about 1.59. This means it has a higher dimension than a line, but a lower dimension than a 2 dimensional shape.

**Square Triangular Numbers**

Square triangular numbers are numbers which are both square numbers and also triangular numbers – i.e they can be arranged in a square or a triangle. The picture above (source: wikipedia) shows that 36 is both a square number and also a triangular number. The question is how many other square triangular numbers we can find?

The equation we are trying to solve is:

a^{2} = 0.5(b^{2}+b)

for some a, b as positive integers. The LHS is the formula to generate square numbers and the RHS is the formula to generate the triangular numbers.

We can start with some simple Python code (which you can run here):

```
```for c in range(1,10001):

for d in range(1,10001):

if c**2 == (d**2+d)/2:

print(c**2, c,d)

This checks the first 10000 square numbers and the first 10000 triangular numbers and returns the following:

1 1 1

36 6 8

1225 35 49

41616 204 288

1413721 1189 1681

48024900 6930 9800

i.e 1225 is the next square triangular number after 36, and can be formed as 35^{2} or as 0.5(49^{2}+49). We can see that there are very few square triangular numbers to be found in the first 50 million numbers. The largest we found was 48,024,900 which is made by 6930^{2} or as 0.5(9800^{2}+9800).

We can notice that the ratio between each consecutive pair of square triangular numbers looks like it converges as it gives:

36/1 = 36

1225/36 = 34.027778

41616/1225 = 33.972245

1413721/41616 = 33.970612

48024900/1413721 = 33.970564

So, let’s use this to predict that the next square triangular number will be around

48024900 x 33.9706 = 1,631,434,668.

If we square root this answer we get approximately 40391

If we solve 0.5(b^{2}+b) = 1,631,434,668 using Wolfram we get approximately 57120.

Therefore let’s amend our code to look in this region:

```
```for c in range(40380,40400):

for d in range(57100,57130):

if c**2 == (d**2+d)/2:

print(c**2, c,d)

This very quickly finds the next solution as:

1631432881 40391 57121

This is indeed 40391^{2} – so our approximation was very accurate. We can see that this also gives a ratio of 1631432881/48024900 = 33.97056279 which we can then use to predict that the next term will be 33.970563 x 1631432881 = 55,420,693,460. Square rooting this gives a prediction that we will use the 235,416 square number. 235,416^{2} gives 55,420,693,056 (using Wolfram Alpha) and this is indeed the next square triangular number.

So, using a mixture of computer code and some pattern exploration we have found a method for finding the next square triangular numbers. Clearly we will quickly get some very large numbers – but as long as we have the computational power, this method should continue to work.

**Using number theory**

The ever industrious Euler actually found a formula for square triangular numbers in 1778 – a very long time before computers and calculators, so let’s have a look at his method:

We start with the initial problem, and our initial goal is to rearrange it into the following form:

Next we make a substitution:

Here, when we get to the equation 1 = x^{2} – 2y^{2} we have arrived at a Pell Equation (hence the rearrangement to get to this point). This particular Pell Equation has the solution quoted above where we can define P_{k} as

Therefore we have

Therefore for any given k we can find the kth square triangular number. The a value will give us the square number required and the b value will give us the triangular number required. For example with k = 3:

This tells us the 3rd square triangular number is the 35th square number or the 49th triangular number. Both these give us an answer of 1225 – which checking back from our table is the correct answer.

So, we have arrived at 2 possible methods for finding the square triangular numbers – one using modern computational power, and one using the skills of 18th century number theory.

**When do 2 squares equal 2 cubes?**

Following on from the hollow square investigation this time I will investigate what numbers can be written as both the sum of 2 squares, 2 cubes and 2 powers of 4. i.e a^{2}+b^{2} = c^{3}+d^{3} = e^{4}+f^{4}.

Geometrically we can think of this as trying to find an array of balls such that we can arrange them into 2 squares, or we can rearrange them and stack them to form 2 cubes, or indeed we can arrange them into 2 4-dimensional cubes. I’ll add the constraints that all of a,b,c,d,e,f should be greater than 1 and that the pair of squares or cubes (etc) must be distinct. Therefore we can’t for example have 2 squares the same size.

**Infinite solutions**

Let’s look at why we can easily find infinite solutions if the squares or cubes (etc) can be the same size.

We want to find solutions to:

a^{2}+b^{2} = c^{3}+d^{3} = e^{4}+f^{4}.

so we look at the powers 2,3,4 which have LCM of 12. Therefore if we choose powers with the same base we can find a solution. For example we chose to work with base 2. Therefore we choose

a = 2^{6}, b = 2^{6}, which gives 2^{12}+2^{12}

c = 2^{4}, d = 2^{4}, which gives 2^{12}+2^{12}

e = 2^{3}, f = 2^{3}, which gives 2^{12}+2^{12}

Clearly these will be the same. So we can choose any base we wish, and make the powers into the same multiples of 12 to find infinite solutions.

**Writing some code**

Here is some code that will find some other solutions:

list1=[]

for a in range(2, 200):

for b in range(2,200):

list1.append(a**2+b**2)

```
```list2=[]

for j in list1:

for c in range(2,200):

for d in range(2,200):

if c**3+d**3 == j:

list2.append(c**3+d**3)

print(list2)

`for k in list2:`

for e in range(2,200):

for f in range(2,200):

if k == e**4+f**4:

print(k,e,f)

This returns the following solutions: 8192, 18737, 76832. Of these we reject the first as this is the solution 2^{12}+2^{12} which we found earlier and which uses repeated values for the squares, cubes and powers of 4. The 3rd solution we also reject as this is formed by 14 ^{4} + 14 ^{4}. Therefore the only solution up to 79202 (we checked every value up to and including 199^{2} + 199^{2}) is:

18737 = 64^{2}+121^{2} = 17^{3}+24^{3} = 11^{4}+8^{4}.

Therefore if we had 18,737 balls we could arrange them into 2 squares, a 64×64 square and a 121×121 square. Alternatively we could rearrange them into 2 cubes, one 17x17x17 and one 24x24x24. Or we could enter a higher dimensional space and create 2 tesseracts one with sides 11x11x11x11 and the other with 14x14x14x14.

With only 1 solution for around the first 80,000 numbers it looks like these numbers are quite rare – could you find another one? And could you find one that also satisfies g^{5}+h^{5}?

**Hollow Cubes investigation**

Hollow cubes like the picture above [reference] are an extension of the hollow squares investigation done previously. This time we can imagine a 3 dimensional stack of soldiers, and so try to work out which numbers of soldiers can be arranged into hollow cubes.

Therefore what we need to find is what numbers can be formed from a^{3}-b^{3}

**Python code**

We can write some Python3 code to find this out (this can be run here):

for k in range(1,200):

```
``` for a in range(0, 100):

for b in range(0,100):

if a**3-b**3 == k :

print(k,a,b)

This gives the following: (the first number is the number of soldiers and the 2 subsequent numbers are the 2 cubes).

1 1 0

7 2 1

8 2 0

19 3 2

26 3 1

27 3 0

37 4 3

56 4 2

61 5 4

63 4 1

64 4 0

91 6 5

98 5 3

117 5 2

124 5 1

125 5 0

127 7 6

152 6 4

169 8 7

189 6 3

We could perhaps investigate any patterns in these numbers, or explore how we can predict when a hollow cube has more than one solution. I’ll investigate which numbers can be written as both a hollow square and also a hollow cube.

**Hollow squares and hollow cubes**

```
```list1=[]

for a in range(2, 50):

for b in range(2,50):

if a**2-b**2 !=0:

if a**2-b**2 > 0:

list1.append(a**2-b**2)

list2=[]

for j in list1:

for c in range(2,50):

for d in range(2,50):

if c**3-d**3 == j:

list2.append(c**3-d**3)

print(list2)

This returns the following numbers which can all be written as both hollow squares and hollow cubes.

[56, 91, 19, 117, 189, 56, 208, 189, 217, 37, 279, 152, 117, 448, 513, 504, 448, 504, 387, 665, 504, 208, 875, 819, 936, 817, 61, 999, 988, 448, 728, 513, 189, 1216, 936, 784, 335, 469, 1323, 819, 1512, 1352, 1197, 992, 296, 152, 1519, 1512, 1197, 657, 1664, 1323, 1647, 1736, 1701, 1664, 936, 504, 2107, 1387, 1216, 1027, 91, 2015, 279, 2232]

**Hollow squares, cubes and hypercubes**

Taking this further, can we find any number which can be written as a hollow square, hollow cube and hollow hypercube (4 dimensional cube)? This would require our soldiers to be able to be stretch out into a 4th dimensional space – but let’s see if it’s theoretically possible.

Here’s the extra code to type:

```
```list1=[]

for a in range(2, 200):

for b in range(2,200):

if a**2-b**2 !=0:

if a**2-b**2 > 0:

list1.append(a**2-b**2)

list2=[]

for j in list1:

for c in range(2,200):

for d in range(2,200):

if c**3-d**3 == j:

list2.append(c**3-d**3)

print(list2)

for k in list2:

for e in range(2,200):

for f in range(2,200):

if k == e**4-f**4:

print(k)

Very pleasingly this does indeed find some solutions:

9919: Which can be formed as either 100^{2}-9^{2} or 22^{3}-9^{3} or 10^{4}-3^{4}.

14625: Which can be formed as either 121^{2}-4^{2} or 25^{3}-10^{3} or 11^{4}-2^{4}.

Given that these took some time to find, I think it’ll require a lot of computer power (or a better designed code) to find any number which is a hollow square, hollow cube, hollow hypercube *and* hollow 5-dimensional cube, but I would expect that there is a number out there that satisfies all criteria. Maybe you can find it?

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

20^{2}-8^{2} = 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 a^{2}-b^{2} = (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 11^{2}-10^{2} = (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 6^{2}-4^{2} = (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?