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
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.
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.
Are you talking about factors or prime factors?
ReplyDeleteThe answer is 5. The solution related to finding number of factors of an integer an Euler's equation. Thanks for the post. Venki.
ReplyDeleten^2 has all the factors of n, plus 2:
ReplyDeleteItself 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
@Gervasious, can you make a formal demostration?
ReplyDeleteI am not sure what formal demonstration means.
ReplyDeleteThis 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.
@codingplayground, Here is my solution.
ReplyDeleteAny 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[1].pdf