Welcome to our community

Be a part of something great, join today!

Find n

Albert

Well-known member
Jan 25, 2013
1,225
$n\in N$

$100\leq n\leq 1997$

$\dfrac{2^n+2}{n} $ also is an integer

please find n
 

Klaas van Aarsen

MHB Seeker
Staff member
Mar 5, 2012
8,864
$n\in N$

$100\leq n\leq 1997$

$\dfrac{2^n+2}{n} $ also is an integer

please find n
I know! I know! (Sun)
Please see my avatar for the method to find n. (Giggle)
 

Klaas van Aarsen

MHB Seeker
Staff member
Mar 5, 2012
8,864
Alternatively:
Code:
perl -e "use bigint; foreach $n (100..1997) { print $n if ((2**$n+2) % $n == 0); }"
946
 

Ackbach

Indicium Physicus
Staff member
Jan 26, 2012
4,197
Alternatively:
Code:
perl -e "use bigint; foreach $n (100..1997) { print $n if ((2**$n+2) % $n == 0); }"
946
Agh! I wanted to do that first on my HP-50g calculator. Alas, I am not familiar enough with programming it.
 

Albert

Well-known member
Jan 25, 2013
1,225
Can this be done without using computer program ?

I mean using mathematical analysis only
 

mathbalarka

Well-known member
MHB Math Helper
Mar 22, 2013
573
Albert.Teng said:
Can this be done without using computer program ?
Same thing I am thinking. The problem can be rephrased as

\(\displaystyle 2^n = -2 \pmod{n}\)

Hence, n isn't prime. In fact, n is also not odd since if it's the case, n would be even and hence, creating a contradiction. See A006517, for example.

I don't there is any analytic way to prove it, the only thing would be brute-force search.
 

Opalg

MHB Oldtimer
Staff member
Feb 7, 2012
2,725
Can this be done without using computer program ?


I mean using mathematical analysis only
I don't see an analytic way to derive this result, but there is a fairly easy way to verify that it is correct.

We want to show that $2^{946} + 2$ is a multiple of $946$. Dividing through by $2$, that is equivalent to showing that $2^{945} + 1$ is a multiple of $473.$ Since $473 = 11\times 43$, it will be enough to show that $2^{945} + 1$ is a multiple of $11$ and also a multiple of $43.$

In the language of congruencies, we need to check that $2^{945}\cong -1\pmod{11}$ and $2^{945}\cong -1\pmod{43}$. But $2^5\cong-1\pmod{11}$ and so $2^k\cong-1\pmod{11}$ whenever $k$ is an odd multiple of $5$. Clearly $945$ is an odd multiple of $5$, and so $2^{945}\cong -1\pmod{11}$. Similarly, $2^7\cong-1\pmod{43}$, and $945$ is an odd multiple of $7$, hence $2^{945}\cong -1\pmod{43}$.

Maybe by looking at that argument more carefully, you could deduce the conditions needed for $2^k+1$ to be a multiple of $k$, and thereby find that $k=473$ is the only solution in the given range.
 

Albert

Well-known member
Jan 25, 2013
1,225
given n=946 and trace back to prove it meets the restriction ,it is easy

but how to get the correct answer n=946 is a challenge

Further more is there any other positive integers will also satisfy our needs ?
 

mathbalarka

Well-known member
MHB Math Helper
Mar 22, 2013
573
Albert.Teng said:
but how to get the correct answer n=946 is a challenge
As I said before, there is a great possibility that there are no other analytical method rather than brute-force.

Albert.Teng said:
Further more is there any other positive integers will also satisfy our needs ?
In the given interval, no. But in \(\displaystyle \mathbb{Z}\), infinitely many and perhaps density as much as \(\displaystyle \mathcal{O}(\log n)\).
 
Last edited:

Bacterius

Well-known member
MHB Math Helper
Jan 26, 2012
644
As I said before, there is a great possibility that there are no other analytical method rather than brute-force.
I have been watching this thread and am assuming Albert has an analytical solution (given this was posted in the Challenges subforum). I would be interested in the solution too, I've been playing around with the problem and am no closer to finding a solution.
 

Albert

Well-known member
Jan 25, 2013
1,225
$n\in N$

$100\leq n\leq 1997$

$\dfrac{2^n+2}{n} $ also is an integer

please find n
in fact we may follow the procedure to find n=946:
(1) at first suppose n is even :
$\dfrac{2^n+2}{n}=2(\dfrac{2^{(n-1)}+1}{2\times a\times b})=\dfrac{2^{(n-1)}+1}{a\times b}$
(here a,b must be odd positive integers)
$=\dfrac {(2^k)^{n-1/k} +1}{ab}-----(*)$ (here k=5,6,7,8 for the last digit of $2^n$ is 2,4,8,6 then repeat )
put k=5 to (*) we get :
$\dfrac {32^{(n-1)/5}+1}{ab}= \dfrac{33\times p}{ab}=m$ (here p is a positive integer )
since $\dfrac {n-1}{5}$ is a positive integer so the last digit of n must be 6 (1 impossible)
if m is an integer then a=11 and p is a multiple of b ,or b=11 and p is a multiple of a
up to now we can conclude that if n is the possible number we need ,and n is even
then the last digit of n is 6 and n is a multiple of 11
$\therefore n=2\times 11 \times (10y+3)$
the last step we must determine the value of y (y may take value 1,2,3,4,5,6,7,8 )
and this is the crucial part how to make sure that y=4
if we put k=7 to (*) we can find b (if a=11) will be 43
for $ 2^5$+1=33 is a multiple of 11
and $2^7$+1=129 is a multiple of 43 ,
$ \therefore $ y=4
that is n is even and n is a multiple of 11 also n is a multiple of 43
and we get $n=2\times 11 \times 43=946$

(2) if n is an odd number
this is impossible as "mathbalarka" wrote
 
Last edited:

mathbalarka

Well-known member
MHB Math Helper
Mar 22, 2013
573
You can exclude the possibility that n is odd and hence, reducing your work a bit.

Albert.Teng said:
(1 impossible)
How does that follow? I don't understand.
 

Albert

Well-known member
Jan 25, 2013
1,225
You can exclude the possibility that n is odd and hence, reducing your work a bit.

Originally Posted by Albert.Teng
(1 impossible)



How does that follow? I don't understand.
take the last digit of $2^n$ into consideration 1 cannot appear

besides n must be even , the last digit of n can not be "1"

so the last digit of n must be "6"
 
Last edited:

mathmaniac

Active member
Mar 4, 2013
188
What answers do the computer programme give?

mathbalarka said:
You can exclude the possibility that n is odd and hence, reducing your work a bit.


n/2 is also odd.
 

mathmaniac

Active member
Mar 4, 2013
188

Albert

Well-known member
Jan 25, 2013
1,225

mathmaniac

Active member
Mar 4, 2013
188

Klaas van Aarsen

MHB Seeker
Staff member
Mar 5, 2012
8,864
What answers do the computer programme give?
The first 6 solutions the computer program gives, are:
1
2
6
66
946
8646

(For bigger numbers we will need to improve the algorithm.)

Btw, n can be odd and n can be prime... but only in the first 2 solutions (1 and 2).
 
Last edited:

mathbalarka

Well-known member
MHB Math Helper
Mar 22, 2013
573
I already gave a link to the sequence in case anyone wants a number of terms to see satisfying everything in the OP except the upper and lower bounds.

mathmaniac said:
So we have to look only numbers of the form 2(mod 4)...
... Which is equivalent to 0 (mod 2) which is not true. Even numbers cannot satisfy the conditions in OP as I noted before. You can't say whether n/2 is odd or even since n/2 isn't really an integer. Hence, your claim that n/2 is odd is false.
 

mathmaniac

Active member
Mar 4, 2013
188
... Which is equivalent to 0 (mod 2) which is not true. Even numbers cannot satisfy the conditions in OP as I noted before.
No.You said odd numbers can't satisfy the condition.
And if you say even numbers can't then what is 6,66,946...etc?Are they odd?

You can't say whether n/2 is odd or even since n/2 isn't really an integer. Hence, your claim that n/2 is odd is false.
I can say.Here is my reasoning.

Edit:I realize it is wrong.

I think I don't even understand how n is not odd....:(

But my claim that n is of the form 2(mod 4) seems to be true for all n.
Coincidence?
 
Last edited:

caffeinemachine

Well-known member
MHB Math Scholar
Mar 10, 2012
834
Same thing I am thinking. The problem can be rephrased as

\(\displaystyle 2^n = -2 \pmod{n}\)

Hence, n isn't prime. In fact, n is also not odd since if it's the case, n would be even and hence, creating a contradiction. See A006517, for example.

I don't there is any analytic way to prove it, the only thing would be brute-force search.
Hello mathbalarka.
I don't see how it follows that $n$ is not odd. Can you please elaborate.
 

mathmaniac

Active member
Mar 4, 2013
188
Hello mathbalarka.
I don't see how it follows that $n$ is not odd. Can you please elaborate.
May I ?

2^n+2 is always even.If n is odd, \(\displaystyle \frac {2^n+2}{n}\) is not an integer and the question is to find n that satisfies \(\displaystyle \frac {2^n+2}{n}\) is an integer.

So n is not odd.

-mathmaniac
 

Bacterius

Well-known member
MHB Math Helper
Jan 26, 2012
644
May I ?

2^n+2 is always even.If n is odd, \(\displaystyle \frac {2^n+2}{n}\) is not an integer and the question is to find n that satisfies \(\displaystyle \frac {2^n+2}{n}\) is an integer.

So n is not odd.

-mathmaniac
[JUSTIFY]The argument does not follow. For instance, 14 is even, yet 7 (an odd number) divides it. What you are essentially saying is that no odd number divides an even number, which is clearly incorrect. This argument is only valid for powers of two, and unfortunately, $2^n + 2$ is never a power of two, except for the case $n = 1$.[/JUSTIFY]
 

mathmaniac

Active member
Mar 4, 2013
188
Looks like I got the fraction upside down in my mind.
Now I am in trouble.Everything seems to be slipping out of my hands.
Let me think...