## Monday, August 23, 2010

### Number puzzle

I was not able to solve it: if an integer n has just 3 factors, how many factors has n^2. Today I learned something new.

#### 6 comments:

1. Are you talking about factors or prime factors?

2. The answer is 5. The solution related to finding number of factors of an integer an Euler's equation. Thanks for the post. Venki.

3. n^2 has all the factors of n, plus 2:
Itself and the product between the two greatest
factors. In total, 5 factors.

i.e
4 has three factors: 1, 2 and 4
16 has five factors: the three of 4 (1,2 and
4), itself (16) and the product between the two
greatest factors of 4 (2x4=8)

the same holds for 9.
9 has 1,3 and 9
81 has 1,3,9,27,81

the same holds for 25
25 has 1,5,25
625 has 1,5,25,125,625

4. @Gervasious, can you make a formal demostration?

5. I am not sure what formal demonstration means.

This piece of code computes the factors for N<10000.

int N = 0, factors = 0, i = 0, square = 0;

for (N = 1; N < 10000; N++) {
factors = 0;
for (i = 1; i <= N; i++) {
if (N % i == 0) {
factors++;
}
}
if (factors == 3) {
printf ("%d has 3 factors\n", N);
square = N * N;
for (i = 1; i <= square; i++) {
if (square % i == 0) {
printf("Factor %d\n", i);
}
}
getchar();
}
}

Now I will attempt to solve it mathematically.

Suppose there is an integer N which apart from
1 and N, it also divides a number x which is
unique.
Hence, N/x = p where p is an integer.

Now we will prove that N^2 divides 1, x, N,
y=N*x and N^2 only.

1. N^2/1=N^2 which is integer
2. N^2/x = N^2/(N/p)=p*N which is integer
3. N^2/N=N which is integer
4. N^2/y=N^2/(N*x)=N/x=p which is integer
5. N^2/N^2=1 which is integer

6. Now we will prove that y is unique.
If it wasn't, then there would be
another int z!=y, so that N^2/z=q, where q is an integer too and q!=p.

Therefore, it would be N^2=z*q.

I found a wall here.

6. @codingplayground, Here is my solution.

Any number other than perfect square will have even number of factors. Only perfect square numbers will have odd number of factors. More generally,

Any number can be expressed as powers of prime factors. The exponents in the power contributes in calculating number of factors the number can have.

For example, say X = a^n * b^m then X can have (n+1)*(m+1) factors which is clearly an even number. This is because atleast one of the exponents (n or m) must be odd, adding 1 to that odd number yields even number hence the overall product. If X is a perfect square then powers of a and b must be 2n and 2m respectively that results in odd number [(2n+1)*(2m+1)].

We can see puzzles on these mathematical properties of numbers. From the book Introduction to Algorithms by Levitin, the first chapter exercises consists of one puzzles on open/close doors.

See second paragraph in third page of the following link.

http://www.maa.org/editorial/euler/How%20Euler%20Did%20It%2037%20Odd%20perfect%20numbers.pdf