# Category Archives: computation

## The Natural Number Game

Hello everyone! It has been quite a while since I have written anything here—my last post was in March 2020, and since then I have been overwhelmed dealing with online and hybrid teaching, plus a newborn (who is now almost … Continue reading

Posted in challenges, computation, proof | Tagged , , , , , | 6 Comments

## More on Human Randomness

In a post a few months ago I asked whether there is a way for a human to reliably generate truly random numbers. I got a lot of great responses and I think it’s worth summarizing them here! Randomness in … Continue reading

Posted in computation, people | Tagged , , , | 2 Comments

## Human Randomness

Randomness is hard for humans It is notoriously difficult for humans to come up with truly random numbers. I don’t really have any data I can point to in particular, but there are quite a few well-known phenomena that show … Continue reading

Posted in computation, people | Tagged , , , | 27 Comments

## Computing the Euler totient function, part 4: totient of prime powers

I’ve been on a bit of a hiatus as I’ve been travelling with my family for the past month. So here’s a recap. Our story so far Recall that the Euler totient function, , counts how many numbers from to … Continue reading

Posted in arithmetic, computation, counting | Tagged , , | Comments Off on Computing the Euler totient function, part 4: totient of prime powers

## Computing the Euler totient function, part 3: proving phi is multiplicative

We are trying to show that the Euler totient function , which counts how many numbers from to share no common factors with , is multiplicative, that is, whenever and share no common factors. In my previous post, we looked … Continue reading

Posted in arithmetic, computation, counting | Tagged , , , | 1 Comment

## Computing the Euler totient function, part 2: seeing phi is multiplicative

In my last post, I claimed that whenever and are relatively prime. (Recall that counts how many numbers from to share no factors in common with .) Let’s get some intuition for this by looking at some Chinese remainder theorem … Continue reading

Posted in arithmetic, computation, counting | Tagged , , | 2 Comments

## Computing the Euler totient function, part 1

Recall that Euler’s totient function counts how many of the integers from to are relatively prime to , that is, share no factors in common with . For example, , since only , , , and share no factors with … Continue reading

Posted in arithmetic, computation, counting | Tagged , , | 1 Comment

## Goldilogs and the n bears

Once upon a time there was a girl named Goldilogs. As she was walking through the woods one day, she came upon a curious, long house. Walking all round it and seeing no one at home, she tried the door … Continue reading

Posted in computation, humor | Tagged , , , , | 1 Comment

## Finding the repetend length of a decimal expansion

We’re still trying to find the prefix length and repetend length of the decimal expansion of a fraction , that is, the length of the part before it starts repeating, and the length of the repeating part. In my previous … Continue reading

| | Comments Off on Finding the repetend length of a decimal expansion

## More on Fermat witnesses and liars

In my previous post I stated, without proof, the following theorem: Theorem: if is composite and there exists at least one Fermat witness for , then at least half of the numbers relatively prime to are Fermat witnesses. Were you … Continue reading

Posted in computation, number theory, primes | Tagged , , , , , | Comments Off on More on Fermat witnesses and liars