MHB Find Integer $n$ in Range $100$ to $1997$

[Albert1]

$n\in N$

$100\leq n\leq 1997$

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

please find n

 

[I like Serena]

$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)

 

[I like Serena]

Alternatively:

perl -e "use bigint; foreach $n (100..1997) { print $n if ((2**$n+2) % $n == 0); }"
946

 

[Ackbach]

Alternatively:

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.

 

[Albert1]

Can this be done without using computer program ?

I mean using mathematical analysis only

 

[mathbalarka]

Can this be done without using computer program ?

Same thing I am thinking. The problem can be rephrased as

$$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]

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.

 

[Albert1]

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]

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.

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

In the given interval, no. But in $$\mathbb{Z}$$, infinitely many and perhaps density as much as $$\mathcal{O}(\log n)$$.

 

[Nono713]

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.

 

[Albert1]

$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

 

[mathbalarka]

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

(1 impossible)

How does that follow? I don't understand.

 

[Albert1]

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

http://www.mathhelpboards.com/images/mhb/misc/quote_icon.png 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"

 

[mathmaniac1]

What answers do the computer programme give?

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

n/2 is also odd.

 

[mathmaniac1]

$ 3^5$+1=33 is a multiple of 11
and $3^7$+1=129 is a multiple of 43 ,

Isn't it "2" instead of 3?

 

[Albert1]

Isn't it "2" instead of 3?

thanks ! yes it is "2" instead of 3

a typo

it has been edited

 

[mathbalarka]

What answers do the computer programme give?

946. You didn't saw page 1 did you? :D

n/2 is also odd.

So? Please elaborate.

 

[mathmaniac1]

So? Please elaborate.

So we have to look only numbers of the form 2(mod 4).So our work is reduced further.

 

[I like Serena]

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).

 

[mathbalarka]

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.

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.

 

[mathmaniac1]

... 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?

 

[caffeinemachine]

Same thing I am thinking. The problem can be rephrased as

$$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.

 

[mathmaniac1]

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, $$\frac {2^n+2}{n}$$ is not an integer and the question is to find n that satisfies $$\frac {2^n+2}{n}$$ is an integer.

So n is not odd.

-mathmaniac

 

[Nono713]

May I ?

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

So n is not odd.

-mathmaniac

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$.​

 

[mathmaniac1]

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...

 

[mathbalarka]

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?

Oops, yes, you are right, it was a typo. But it still doesn't follow that n/2 have to be odd, you don't have a proof!

EDIT : Is it a coincidence that n/2 is odd for n satisfying < 500000000? I think we can prove it if we can prove that all such n ends with the digit 6.

 

[mathbalarka]

I don't see how it follows that n is not odd. Can you please elaborate.

It's not that straightforward as mathmaniac thinks it is. I already gave the link but nobody have seen it. Here it is one more time for the readers and contributers of this topic : A006517. (Look at the comment of Max Aleksevev)

 

[caffeinemachine]

It's not that straightforward as mathmaniac thinks it is. I already gave the link but nobody have seen it. Here it is one more time for the readers and contributers of this topic : A006517. (Look at the comment of Max Aleksevev)

Thanks. Nice.