# Function that tells if number is prime, perfect square or other composite.

There was a math function (studied by Euler, but I might be wrong) that takes a number and maps it on one of three classes: "prime", "perfect square", "composite, but not square" represented as $-1$, or $0$, or $1$

What is the name of this function?

I don't know of Euler studying a function meeting your description. It sounds like you have a slightly garbled version of the Mobius function https://en.wikipedia.org/wiki/Mobius_function . $\mu(n)$ satisfies that $\mu(n)=0$ when $n$ is divisible by a perfect square greater than 1. When $n$ is square free, $\mu(n)=1$ when $n$ has an even number of prime factors, while $\mu(n)=-1$ when $n$ has an odd number of prime factors. Is this what you were thinking of?

• This is the function I was looking for. – Stepan Aug 19 '18 at 1:48

There was a math function? It no longer is? I'm not saying this to be a jerk, I'm saying it to make the point that mathematical objects exist regardless of what we call them or even if we don't know about them.

But in this case of the function that you're thinking about, it would of course really help you if you knew what it's called.

How can you figure that out? The OEIS might help. Compute the values of the function for the first few $n$ (it's often a good idea to skip 1 and start at 2) and look it up in the OEIS: $$-1, -1, 0, -1, 1, -1, 1, 0, 1, -1, 1, -1, 1, 1, 0, -1, 1, -1, 1, 1, 1, -1, 1, 0$$

Hmm... nine results, but only one result matches the signs, A068717, $x^2 - ny^2 = \pm 1$ has infinitely many solutions in integers $(x, y)$. I admit I don't completely understand this entry.

Nor can I be sure that I would have thought of the Möbius function $\mu(n)$ if JoshuaZ hadn't mentioned it.

I may have or may not have thought of this adjustment to the function: $f(n) = 0$ if $n$ is divisible by a square even if not itself a square.

A square is still trivially divisible by itself. But numbers like 8, 12, 18, 20, 24, 27, 28, etc., are also each divisible by at least one square.

With this adjustment, our search query becomes $$-1, -1, 0, -1, 1, -1, 0, 0, 1, -1, 0, -1, 1, 1, 0, -1, 0, -1, 0, 1, 1, -1, 0, 0$$ and the first result is A008683, Möbius function $\mu(n)$. $\mu(1) = 1$, $\mu(n) = (-1)^k$ if $n$ is the product of $k$ different primes; otherwise $\mu(n) = 0$.

This function is more elegant because it's multiplicative, which means that if $\gcd(m, n) = 1$, then $\mu(mn) = \mu(m) \mu(n)$.

You can't say that about the other function, because, for example, $f(30) = 1$ (on account of being composite but not square) but $f(2) = -1$ (on account of being prime) and $f(15) = 1$ (on account of being composite but not square).

By comparison $\mu(30) = -1$ (on account of having an odd number of distinct prime factors with no repetition) and $\mu(2) = -1$ (on account of being prime) and $\mu(15) = 1$ (on account of having an even number of distinct prime factors with no repetition).

Since a prime number has an odd number of prime factors (namely 1), your confusion was understandable.

• The OEIS is a great resource iff you know the exact behavior of the object. I wrongly assumed that only squares yield zero, so my sequence was incorrect at m(8) – Stepan Aug 19 '18 at 20:45
• The folks at the OEIS would disagree with you and perhaps take offense at your "if and only if." But sequences of 0s and 1s can be quite a pain to search for, though. – Robert Soupe Aug 20 '18 at 3:18