Fast Exponentiation, revisited

12/11/2019

Quite a while ago, I presented a fast exponentiation algorithm that uses the binary decomposition of the exponent n to perform O(\log_2 n) products to compute x^n.

While discussing this algorithm in class, a student asked a very interesting question: what’s special about base 2? Couldn’t we use another base? Well, yes, yes we can.

Read the rest of this entry »


Count like an Egyptian (Part III)

11/10/2016

In previous posts, I’ve looked into unit fractions, also known as “Egyptian fractions”, fractions where the numerator is 1 and the denominator n, some integer. We have noticed that finding good representation for a fraction a/b as a sum of unit fraction is not as trivial as it may first seem. Indeed, we noticed that the greedy algorithm, the one that always pick the largest unitary fraction that does not exceed the rest as the next term, may lead to long series of unit fractions, sometimes with large denominators, even for simple fraction. For example,

\displaystyle \frac{412}{1000}=\frac{103}{250}=\frac{1}{3}+\frac{1}{13}+\frac{1}{574}+\frac{1}{699563}.

In a previous post, I suggested decomposing a/b in an “easy way”, which was often better than the greedy algorithm. Surely, we can do better, but how?

Read the rest of this entry »


Jouette’s Attractor

16/09/2014

I have been reading a lot of mathematical recreation books of late. Some in English, some in French, with the double goal of amusing myself and of finding good exercises for my students. In [1], we find the following procedure:

Take any number, n digits long, make this number t. Make t_1 the number made of the sorted (decreasing order) digits of t, and t_2, the number made of the sorted (increasing order) digits of t. Subtract both to get t': t'=t_1-t_2. Repeat until you find a cycle (i.e., the computation yields a number that have been seen before).

Jouette states that for 2 digits, the cycle always starts with 9, for 3 digits, it starts with 495, for 4 digits, 6174, and for 5 digits, 82962. For 2, 3, and 4 digits, he’s mostly right, except that the procedure can also reach zero (take 121 for example: 211-112=99, 99-99=0). For 5 digits, however, he’s really wrong.

Read the rest of this entry »


Take That, Fermat!

02/09/2014

You’ve certainly heard of Fermat’s last theorem stating that

x^n+y^n=z^n

has no integer solutions for n\geqslant{3}. Well, guess what:

85751^{12} + 95642^{12} = 97565^{12}.

Take that, Fermat!

Read the rest of this entry »


Count Like an Egyptian (Part II)

22/04/2014

In a previous entry, we discussed egyptian fractions and, in particular, a greedy algorithm to convert them. We noticed that, once in a while, the greedy algorithm generates a really large denominator, despite harmless-looking fractions:

\displaystyle \frac{412}{1000}=\frac{1}{3}+\frac{1}{13}+\frac{1}{574}+\frac{1}{699563}

So, I had an idea to, maybe, minimize the size of the maximum denominator.

Read the rest of this entry »


Simple Random Generators

15/10/2013

We all need (pseudo)random numbers sooner or later. Are they hard to generate? Depends. If you want them to be really strong (that is, very random), yes, it’s difficult. If you merely need something random-looking, well, you still need some number theory, but it’s rather not complicated.

roulette

Let’s have a look at three simple types: additive, multiplicative, and the infamous linear congruential generator.

Read the rest of this entry »


Amicable Numbers (part I)

20/08/2013

I know of no practical use for Amicable numbers, but they’re rather fun. And rare. But let’s start with a definition. Let n be a natural number (a positive integer), and let

\displaystyle \sigma(n)=\sum_{d|n}d

with d \in \mathbb{N} and 1\leqslant{d}\leqslant{n}, be the sum of the divisors of n. We’re in fact interested in the sum of the proper divisors of n, that is,

s(n)=\sigma(n)-n

Now we’re ready to define amicable numbers!

Amicable numbers: Two numbers, n, m \in \mathbb{N} are amicable, if, and only if, s(n)=m and s(m)=n.

Given n, we can find m=s(n) and test if n=s(m)=s(s(n)). But to do that efficiently, we need to compute s(n) (or \sigma(n)) very rapidly. The first expression above requires O(n), but we can do much better. Let’s see how.

Read the rest of this entry »


The conjecture of 8

23/07/2013

The other day I found an amusing short from numberphile about “happy numbers”. Not unlike the Collatz problem, a number is happy if, through successive transformations, it reaches one. The transformation is rather numerological in nature (i.e., it’s arbitrary and so why not): To get the next number in the series to happiness, you take the current number and sum the squares of its digits.

The example in the video is that 7 is a happy number:

7 \to 7^2=49

49 \to 4^2+9^2=97

97 \to 9^2+7^2=130

130 \to 1^2+3^2+0^2=10

10 \to 1^2+0^2=1

Therefore 7 is a happy number. That’s cool, but are all numbers happy, and, if not, what happens when a number is unhappy?

Read the rest of this entry »


On rectangles

19/02/2013

While reading Cryptography: The Science of Secret Writing [1], the author makes a remark (p. 36) (without substantiating it further) that the number of possible distinct rectangles composed of n squares (a regular grid) is quite limited.

Mondrian_CompRYB

Unsubstantiated (or, more exactly, undemonstrated) claims usually bug me if the demonstration is not immediate. In this case, I determined fairly rapidly the solution, but I guess I would have liked something less vague than “increased in size does not necessarily provide greater possibilities for combination.” Let’s have a look at that problem.

Read the rest of this entry »


Different problems aren’t always different

21/04/2009

Magic Squares are much less frequent than latin squares in computer science (on which we may come back in the future), but they have a number of (fun) applications.

Historically, magic squares are tied to numerology, alchemy and other esoteric sytems. However, as you may already know, I’m not interested in pseudoscience except to debunk it, so this post isn’t about using magic squares turtles to predict the level of the river running behind your house.

Albrech Dürer's Melancholia I

Albrech Dürer's Melancholia I

Read the rest of this entry »