| T.R | Title | User | Personal
Name | Date | Lines |
|---|
| 1804.1 | | HANNAH::OSMAN | see HANNAH::IGLOO$:[OSMAN]ERIC.VT240 | Wed Oct 06 1993 11:54 | 16 |
|
> 4 n
>Prove that n + 4 is non-prime for all n > 1.
n^4 + 4^n = n^4 + (2^n)^2 = (n^2)^2 + (2^n)^2 = a^2 + b^2
Am I close ?
/Eric
|
| 1804.2 | | RUSURE::EDP | Always mount a scratch monkey. | Wed Oct 06 1993 14:34 | 29 |
| Re .0:
Solution found with help of computer algebra:
Divide n by 10, yielding n = 10*q + r.
If r is even, then n^4+4^n is clearly even and greater than 2, so it is
composite.
If r is 1, 3, 7, or 9, then n^4 is congruent to 1 modulo 5. And n is
odd for these r, so 4^n is congruent to 4 modulo 5, so n^4+4^n is
divisible by 5 and clearly greater than 5.
If r is 5, then n^4+4^n = (10*q+5)^4 + 4^(10*q+5) =
[ 2^(10*q+5) - 5*(2q+1)*2^(5q+3) + 25(2q+1)^2 ] *
[ 2^(10*q+5) + 5*(2q+1)*2^(5q+3) + 25(2q+1)^2 ].
Both factors are clearly greater than one when q is non-negative, so
n^4+4^n is composite in all cases when n>1.
Derive provided the factorization easily; Maple did not.
-- edp
Public key fingerprint: 8e ad 63 61 ba 0c 26 86 32 0a 7d 28 db e7 6f 75
To get PGP, FTP /pub/unix/security/crypt/pgp23A.zip from nic.funet.fi.
|
| 1804.3 | | AUSSIE::GARSON | Hotel Garson: No Vacancies | Wed Oct 06 1993 19:48 | 71 |
| re .2
It can be done a little more simply because the expression in n
factorises directly for odd n. I don't know whether you can persuade
Derive to spot it.
4 n
Let u = n + 4
For even n obviously 16|u so u is non-prime.
Otherwise, observe that
( 2 n )� 2 n
u = (n + 2 ) - 2n � 2
( 2 n )� 2 (n+1)
= (n + 2 ) - n � 2
and where n is odd, 2|n+1 so we may continue
( 2 n )� ( (n+1)/2 )�
= (n + 2 ) - (n � 2 )
( 2 n (n+1)/2 ) ( 2 n (n+1)/2 )
= (n + 2 + n � 2 ) � (n + 2 - n � 2 )
The left hand factor is obviously > 1 for all positive integers, n. The right
hand factor is = 1 only for n = 1. Hence we have a factorisation that makes t
non-prime for odd n > 1.
Hence t is non-prime for all n > 1.
Generalisation
==============
For arbitrary s >= 1, t >= 0
Let u = n^(4s)+(2^(4t+2))^n
As above, n even => 16|u
For n odd put
u = (n^(2s)+(2^(2t+1))^n)� - (n^s�2^(((2t+1)n+1)/2))� = L � R
and define
x = n^s (so clearly x >= 1)
y = 2^(((2t+1)n+1)/2) (also clearly y >= 2)
so that (skipping some steps)
L = �[(x+y)�+x�] and R = �[(x-y)�+x�]
Obviously L > 1 for any positive integer, n.
Let R=1
=> (x-y)�+x� = 2
=> x = 1 and x-y = -1
i.e. x = 1 and y = 2
x = 1 => n = 1
and
y = 2 => n = 1 and t = 0
Hence it has been shown that u is non-prime for all s, t and n - except that the
case where t = 0 and n = 1 has not been covered, and in fact where t = 0 and
n = 1, u = 5 (regardless of s) i.e. u is prime.
|
| 1804.4 | | RUSURE::EDP | Always mount a scratch monkey. | Thu Oct 07 1993 09:42 | 11 |
| Re .3:
> I don't know whether you can persuade Derive to spot it.
Yes, when I enter n^4+4^n and substitute 2j+1 for n, Derive factors the
result easily. It works surprisingly well in factoring and simplifying
expressions, handling cases that Maple does not or that Maple is
awkward at.
-- edp
|
| 1804.5 | .3 is obvious in hindsight! | TROOA::RITCHE | From the desk of Allen Ritche... | Thu Oct 07 1993 15:47 | 22 |
|
RE: .3, Derek,
Yes.. nice solution!
> ( 2 n (n+1)/2 ) ( 2 n (n+1)/2 )
> = (n + 2 + n � 2 ) � (n + 2 - n � 2 )
>
I used a similar approach to .2, i.e. consider only odd n in which
case F(n) = n^4 + 4^n == 1 mod 5 + 4 mod 5 == 0 mod 5 (where n is not mod 5).
Considering the case n=5k, I couldn't factor (625k^4 + 1024^k) in time to
finish it off.
> It can be done a little more simply because the expression in n
> factorises directly for odd n. I don't know whether you can persuade
> Derive to spot it.
What is "Derive" and where can I get it?
Allen
|
| 1804.6 | | RUSURE::EDP | Always mount a scratch monkey. | Thu Oct 07 1993 17:03 | 17 |
| Re .5:
Derive is a symbolic math program available from Soft Warehouse, 3660
Waialae Avenue, Suite 304, Honolulu, HI, 96816-3236. It is also sold
by Educalc, 1-800-677-7001. It runs under DOS on PCs, including the
HP-95 palmtop. It has an excellent character-based interface; it
manages to draw expressions reasonably well. It's not as fancy as
Maple with a Windows interface, and it doesn't have the humongous
library of functions, but it actually does better than Maple and
Mathematica at many factorizations and simplifications.
-- edp
Public key fingerprint: 8e ad 63 61 ba 0c 26 86 32 0a 7d 28 db e7 6f 75
To get PGP, FTP /pub/unix/security/crypt/pgp23A.zip from nic.funet.fi.
|
| 1804.7 | | AUSSIE::GARSON | Hotel Garson: No Vacancies | Fri Oct 08 1993 00:01 | 31 |
| re .5
I should point out that neither the original problem nor the solution
is due to me. (I haven't the faintest who first came up with it. Given
the relative simplicity I would imagine it's not recent.)
re .1
> Am I close?
On the right track. You have to write a^2 + b^2 as (a+b)^2-2ab and then
realise that 2ab is itself a perfect square.
re .4
While I was myself looking at this problem I observed the following...
odd n u prime fact. of u
3 145 5 . 29 (4^1+1)�(...)
5 1649 17 . 97 (4^2+1)�(...)
7 18785 5.13 . 17.17 (4^3+1)�(...)
9 268705 5.61 . 881 (4^4+7�)�(...)
11 4208945 5.13.17 . 13.293 (4^5+9�)�(...)
13 67137425 37.181 . 5.5.401 (4^6+51�)�(...)
15 1073792449 29153 . 36833 (4^7+113�)�(...)
(The prime factorisation is not grouped in the normal way in order to
show which factors I used to produce the last column.)
Is this pattern real? I couldn't get a factor of the form (4^n+a^2) to
fall out even after I had a working proof.
|
| 1804.8 | yup | HERON::BUCHANAN | The was not found. | Fri Oct 08 1993 08:01 | 27 |
| > While I was myself looking at this problem I observed the following...
>
>odd n u prime fact. of u
>3 145 5 . 29 (4^1+1)�(...)
>5 1649 17 . 97 (4^2+1)�(...)
>7 18785 5.13 . 17.17 (4^3+1)�(...)
>9 268705 5.61 . 881 (4^4+7�)�(...)
>11 4208945 5.13.17 . 13.293 (4^5+9�)�(...)
>13 67137425 37.181 . 5.5.401 (4^6+51�)�(...)
>15 1073792449 29153 . 36833 (4^7+113�)�(...)
> Is this pattern real?
Yes. The factors of u that you found are of the form:
n^2 + 2^n � n*2^((n+1)/2)
= n^2 + 2^(n-1) � n*2^((n+1)/2) + 2^(n-1)
= (n � 2^((n-1)/2))^2 + 4^((n-1)/2)
This yields terms agreeing with your table above, except that for n=11,
I find:
u = (4^5+21�).(4^5+43�)
Certainly, 4^5+9� divides u, but the quotient is not of the form we're
interested in. I suspect it's un hareng rouge.
Cheers,
Andrew.
|
| 1804.9 | | CFSCTC::GILBERT | | Fri Oct 08 1993 14:59 | 3 |
| What about n^6 + 6^n ?
What about n^5 + 5^n ? Does it generate an infinite number of primes?
|
| 1804.10 | | AUSSIE::GARSON | Hotel Garson: No Vacancies | Sat Oct 09 1993 01:10 | 50 |
| re .8
Ayep, thanks Andrew.
>Certainly, 4^5+9� divides u, but the quotient is not of the form we're
>interested in.
Bit of bad luck that, eh!
>I suspect it's un hareng rouge.
It loses something in the translation. Une fausse piste, peut-�tre.
re .9
Clearly n^6+6^n cannot be prime where 2|n or 3|n i.e. we need consider
only the case that n mod 6 = �1 (if that helps).
Anyway here's some raw data (e. & o.e.) ...
u = n^5+5^n
n = 14 u = 1809086153 7 43 53 151 751
n = 13 u = 1221074418 2 3 203512403
n = 12 u = 244389457 13 19 463 2137
n = 11 u = 48989176 2 2 2 31 251 787
n = 10 u = 9865625 5 5 5 5 5 7 11 41
n = 9 u = 2012174 2 1006087
n = 8 u = 423393 3 141131
n = 7 u = 94932 2 2 3 3 3 3 293
n = 6 u = 23401 7 3343
n = 5 u = 6250 2 5 5 5 5 5
n = 4 u = 1649 17 97
n = 3 u = 368 2 2 2 2 23
n = 2 u = 57 3 19
n = 1 u = 6 2 3
u = n^6+6^n
n = 11 u = 364568617 7 52081231
n = 10 u = 61466176 2 2 2 2 2 2 37 101 257
n = 9 u = 10609137 3 3 3 3 3 3 3 3 3 7 7 11
n = 8 u = 1941760 2 2 2 2 2 2 2 2 5 37 41
n = 7 u = 397585 5 131 607
n = 6 u = 93312 2 2 2 2 2 2 2 3 3 3 3 3 3
n = 5 u = 23401 7 3343
n = 4 u = 5392 2 2 2 2 337
n = 3 u = 945 3 3 3 5 7
n = 2 u = 100 2 2 5 5
n = 1 u = 7 7
|