Author: mathsbyagirl

Maths Cakes

After arriving from my one week holiday abroad, I thought I’d write a bit of a fun post inspired by an article I read on mymordernmet about math cakes.

Dinara Kasko, former architect who is now a baker, has created a series of cakes inspired by art and mathematics. Whilst Kasko employs fascinating processes to make the original cakes, they are composed of conventional ingredients. With the use of algorithmic tools and complex diagramming techniques, Kasko cakes reminisce “3D graphs, geometric models, and avant-garde sculptures.

 

M x

Advertisements

Lychrel numbers

Lychrel number is a natural number that cannot form a palindrome by the 196-algorithm: an iterative process of repeatedly reversing a numbers’ digits and adding the resulting numbers.

Whilst in other bases (powers of two) certain numbers can be proven to never form a palindrome, in base 10 (the base system we use in everyday life) no Lychrel numbers have been proven to exist. However many numbers, such as 196, are suspected to be a Lychrel number on “heuristic and statistical grounds“.

The name Lychrel was coined by Wade Van Landingham in 2002 as an anagram of Cheryl, his girlfriend’s name.

196-Algorithm

The reverse-and-add process is when you add a number to the number formed by reversing the order of its digits.

Examples of non-Lychrel numbers are (taken from Wikipedia):

  • 56 becomes palindromic after one iteration: 56+65 = 121.
  • 57 becomes palindromic after two iterations: 57+75 = 132, 132+231 = 363.
  • 59 becomes a palindrome after 3 iterations: 59+95 = 154, 154+451 = 605, 605+506 = 1111
  • 89 takes an unusually large 24 iterations to reach the palindrome 8,813,200,023,188.
  • 1,186,060,307,891,929,990 takes 261 iterations to reach the 119-digit palindrome 44562665878976437622437848976653870388884783662598425855963436955852489526638748888307835667984873422673467987856626544, which is the current world record for the Most Delayed Palindromic Number. It was solved by Jason Doucette‘s algorithm and program in 2005.

196

196 is the smallest number suspected to never reach a palindrome in base 10 and has thus received the most attention:

  • In 1985 a program by James Killman ran unsuccessfully for over 28 days, cycling through 12,954 passes and reaching a 5366-digit number.
  • John Walker began his 196 Palindrome Quest in 1987. His program ran for almost three years, then terminated (as instructed) in 1990 with the message:

    Stop point reached on pass 2,415,836.
    Number contains 1,000,000 digits.
  • In 1995, Tim Irvin and Larry Simkins reached the two million digit mark in only three months without finding a palindrome.
  • Jason Doucette then reached 12.5 million digits in May 2000.
  • Wade Van Landingham used Jason Doucette’s program to reach a 13 million digit. By May 2006, Van Landingham had reached the 300 million digit mark.
  • In 2011 Romain Dolbeau completed a billion iterations to produce a number with 413,930,770 digits, and in February 2015 his calculations reached a number with billion digits.

 A palindrome has yet to be found.

For more on Lychrel numbers, click here or here.

M x

 

VIDEO: Where Algorithms Fail

My sister showed me this video a few days ago and I’d thought I’d share it with you. In it Cathy O’Neil, author of the new book ‘Weapons of Math Destruction‘, discusses the danger of algorithms, giving a few examples to illustrate her eye-opening points. O’Neil then goes on to highlight a few steps we can take, as a society, in order to overcome these pitfalls. I found this short video thoroughly interesting and hope you enjoy it as well!

“Algorithms decide who gets a loan, who gets a job interview, who gets insurance and much more — but they don’t automatically make things fair. Mathematician and data scientist Cathy O’Neil coined a term for algorithms that are secret, important and harmful: “weapons of math destruction.” Learn more about the hidden agendas behind the formulas.”

M x

NEWS: New Prime Found

On August 29th PrimeGrid discovered the largest generalised Fermat Prime:

Screen Shot 2017-09-04 at 5.48.11 PM.png

A generalised Fermat Prime is a prime number of the form Screen Shot 2017-09-04 at 5.46.30 PM.png for a >0. It is called ‘generalised’ as a Fermat Prime is a number of this form with a = 0.

The discovery was made by Sylvanus A. Zimmerman of the United States.

“Until now only 392 generalised Fermat primes had been found: this new discovery makes 393. At 6,253,210 digits long, it’s now the 12th largest of all known primes, and the second-largest known non-Mersenne prime.”

-Aperiodical

M x

Ramsey’s Theorem

Ramsey’s theorem is a fundamental theorem in combinatorial mathematics, and initiated the combinatorial theory called Ramsey Theory. This theory aims to seek regularity in disorder: “general conditions for the existence of substructures with regular properties“.

Ramsey’s theorem states that:

“for each pair of positive integers k and l there exists an integer R(k,l) such that any graph with R(k,l) nodes contains a clique with at least k nodes or an independent set with at least l nodes.


Clique:

A clique of agraph G is a complete subgraph of G.

Clique_950.gif

Source: MathWorld

Independent Set:

An independent vertex set of a graph is a subset of the vertices such that no two vertices in the subset represent an edge of the graph. Below are some examples:

IndependentSet_900.gif

Source: MathWorld


Another formulation of the theorem states that “there exists a least positive integer R(rs) for which every blue-red edge colouring of the complete graph on R(rs) vertices contains a blue clique on vertices or a red clique on s vertices”. Extending this theorem, we can apply this to n colours rather than just 2.

For a proof of this theorem, click here.

Ramsey Numbers

The numbers R(r,s) in Ramsey’s theorem are called Ramsey numbers. Ramsey numbers give the solution to the party problem that asks:

“the minimum number of guests, R(mn), that must be invited so that at least m will know each other or at least n will not know each other”

Connecting Ramsey numbers to graph theory, the Ramsey number is the minimum number of vertices, v = R(m,n), needed in order for all undirected graphs of order v to contain a clique of order m or an independent set of order n. Ramsey’s theorem tells us that this exists for all m and n.

Click here for an article on how to calculate R(4,3).

M x

MATHS BITE: Ford Circles

A ford circle is a circle with centre (p/q,1/(2q^{2})), and radius 1/(2q^{2}), where p and q are coprime integers.

File:Ford circles colour.svg

Source: Wikipedia

Notice that each Ford Circle is tangent to to the horizontal axis and any two Ford circles are either tangent or disjoint. The latter statement can be proven by finding the squared distance d^2 between the centres of the circles with (p,q) and (p’,q’) as the pairs of coprime integers.

latex-image-1.png

Let s be the sum of the radii:

latex-image-2.png

Then

latex-image-3.png

However, we have that latex-image-4.png and so latex-image-5.png, thus the distance between circles is greater or equal to the sum of the radii of the circles. There is equality iff

latex-image-6.png

In this case, the circles are tangent to one another.

Total area of Ford Circles

(taken from Wikipedia)

As no two ford circles intersect, it follows immediately that the total area of the Ford circles:

\left\{C[p,q]:0\leq {\frac  {p}{q}}\leq 1\right\}

is less than 1.

From the definition, the area is

A=\sum _{{q\geq 1}}\sum _{{(p,q)=1 \atop 1\leq p<q}}\pi \left({\frac  {1}{2q^{2}}}\right)^{2}.

Simplifying this expression gives us

A={\frac  {\pi }{4}}\sum _{{q\geq 1}}{\frac  {1}{q^{4}}}\sum _{{(p,q)=1 \atop 1\leq p<q}}1={\frac  {\pi }{4}}\sum _{{q\geq 1}}{\frac  {\varphi (q)}{q^{4}}}={\frac  {\pi }{4}}{\frac  {\zeta (3)}{\zeta (4)}},

noting that the last equality is given by considering the Dirichlet generating function for Euler’s totient function φ(q).

Given that ζ(4) = π^4/90, we get

A={\frac  {45}{2}}{\frac  {\zeta (3)}{\pi ^{3}}}\approx 0.872284041.

O_79.pngM x

Last Digit

How would we go about finding the last digit of very large numbers, such as Screen Shot 2017-08-24 at 4.27.22 PM.png?

There are a variety of different tools that we can use, including modular arithmetic and the Chinese remainder theorem, which I am going to talk about in today’s post.

Pattern Finding

A problem like this can be tackled by listing out the initial expansions of a power in order to determine a pattern. Then, by proving that this pattern holds (often by induction), the last decimal digit of a power can be solved completely. For example, the last digit of various powers of 1 to 9 are:

Screen Shot 2017-08-24 at 4.32.26 PM.png

Source: Brilliant

From this we can determine that:

  • the last digit of powers of 1 is always 1;
  • the last digits of powers of 2 repeat in a cycle of 4, 8, 6, 2;
  • the last digits of powers of 3 repeat in a cycle of 9, 7, 1, 3;
  • the last digits of powers of 4 alternate between 6 and 4;
  • the last digit of powers of 5 is always 5;
  • the last digit of powers of 6 is always 6;
  • the last digits of powers of 7 repeat in a cycle of 9, 3, 1, 7;
  • the last digits of powers of 8 repeat in a cycle of 4, 2, 6, 8;
  • the last digits of powers of 9 alternate between 1 and 9.

Example

Find the last digit of 2^2016.

The last digits of the powers of two repeat in a cycle of 4, 8, 6, 2. Dividing 2016 by 4 we get 504 (with no remainder). Hence the sequence of digits repeats 504 times with no extra entries, so the last digit should be 6. 

Modular Arithmetic

The above idea can be expressed more elegantly with modular arithmetic. Finding the last digit of a number is the same as finding the remainder when this number is divided by 10. In general, the last digit of a power in base n is its remainder upon division by n. So, for decimal numbers, we compute mod 10 to find the last digit, mod 100 to find the last two digits, etc.

For example,

Screen Shot 2017-08-24 at 5.22.44 PM.png

Chinese Remainder Theorem

The Chinese Remainder Theorem states that

if one knows the remainders of the division of an integer n by several integers, then one can determine uniquely the remainder of the division of n by the product of these integers, under the condition that the divisors are pairwise coprime

– Wikipedia

Applying this theorem, we can find a number mod 2^n and mod 5^n and then combine those results to find that number mod 10^n.

Example

Find the last two digits of 74^540.

Observe that 100 = 4 x 25 and gcd(4,25) = 1. So we can compute 74^540 mod 4 and mod 25, then combine these to find it mod 100. 

74^540 ≡ 2^540 x 37^540 ≡ 0 (mod 4)

and 

7^540 ≡ (-1)^540 ≡ 1 (mod 25)

The unique solution mod 100 to x ≡ 0 (mod 4), x ≡ 1 (mod 25) is 76, so this is the answer.

Euler’s Theorem

Euler’s Theorem states that

“if n and a are coprime positive integers, then

a^{\varphi (n)} \equiv 1 \pmod{n}

where \varphi (n) is Euler’s totient function.”

-Wikipedia

So an exponent b can be reduced modulo φ(n) to a smaller exponent without changing the value of a^b (mod n).

Example

Find the last two digits of 33^42.

φ(100) = 40, so 33^40≡ 1 (mod 100). So, 33^42 ≡ 33^2 (mod 100). This is easier to compute: 33^2 = 1089, so answer is 89.

Binomial Expansion

Another method is to expand the power using the Binomial theorem in such a way that many of the terms vanish mod 10. This is generally only useful when the base of the exponent is of the form 10k +/- 1.

Example

Find the last two digits of 31^25.

Screen Shot 2017-08-24 at 5.39.04 PM.png

After the second term, every term contains at least 2 zeros, and so they vanish mod 100. The first two terms = 751 ≡ 51 (mod 100) and so the last two digits of 31^25 are 51.

Hope you enjoyed this slightly longer post! M x