My Math Forum  

Go Back   My Math Forum > College Math Forum > Number Theory

Number Theory Number Theory Math Forum


Thanks Tree6Thanks
Reply
 
LinkBack Thread Tools Display Modes
July 31st, 2015, 07:54 AM   #1
Banned Camp
 
Joined: Dec 2013

Posts: 1,117
Thanks: 41

Conjecture "2^n"

n positive integer > 0

Let us define a function S(k)

S(n)=2^n
S(n-1)=S(n)-(2^n-1)
S(n-2)=S(n-1)+(2^n-2)
S(n-3)=S(n-2)-(2^n-3)
....
S(0)=S(1)+ or - (2^0)

We start with the sign + and we alternate -+-+-+....

Example n=5

S(5)=2^5=32
S(4)=2^5-2^4=32-16=16
S(3)=16+2^3=24
S(2)=24-2^2=20
S(1)=20+2=22
S(0)=22-(2^0)=22-1=21

Here is my conjecture "2^n"

For each n>0 it always exist at least a number k such as n divide S(k)

For n=5
5 divide S(2)=20

19 divide S(11)
13 divide S(2) and so on

Is there any counter-example?
Can we prove the conjecture?

Thank you.
mobel is offline  
 
July 31st, 2015, 04:11 PM   #2
Senior Member
 
Joined: Aug 2012

Posts: 2,356
Thanks: 738

Quote:
Originally Posted by mobel View Post
For each n>0 it always exist at least a number k such as n divide S(k)

For n=5
5 divide S(2)=20
To begin, your notation's not very good. Because if I ask you what is $\displaystyle S(3)$, then it's $\displaystyle 2^3 = 8$. But if you started from $\displaystyle n = 5$, then $\displaystyle S(3) = 24$. So $\displaystyle S$ is not a function.

Your procedure does generate a sequence of numbers though, so let's see if we can analyze that.

Given $\displaystyle n$, your sequence is:

$\displaystyle 2^n$

$\displaystyle 2^n - 2^{n-1}$

$\displaystyle 2^n - 2^{n-1} + 2^{n-2}$

$\displaystyle 2^n - 2^{n-1} + 2^{n-2} - 2^{n-3}$

...

(*) $\displaystyle 2^n - 2^{n-1} + 2^{n-2} - 2^{n-3} \dots \pm 1$

If $\displaystyle n$ is odd, then the final term is $\displaystyle +1$; if $\displaystyle n$ is odd, the final term is $\displaystyle -1$.

Do you agree so far? I want to make sure I'm understanding your procedure.

Now, your question is a little confusing. You asked

Quote:
Originally Posted by mobel View Post
For each n>0 it always exist at least a number k such as n divide S(k)

For n=5
5 divide S(2)=20
Your example doesn't match what you wrote. If I pick $\displaystyle n = 47$, you are asking if there is some $\displaystyle k$ for which $\displaystyle 47$ divides $\displaystyle S(k)$. But we've already seen that the expression $\displaystyle S(k)$ is not well-defined. Do you mean one of the members of the sequence generated by $\displaystyle 47$?

If so, I think your question is whether $\displaystyle n$ always divides at least one of the partial sums of expression (*).

Does that sound about right?

(edit) As I look at it, this is an interesting problem in modular arithmetic. Look at the example for $\displaystyle n = 5$. Our (*) series is:

$\displaystyle 2^5 - 2^4 + 2^3 - 2^2 + 2 - 1$.

Now look at the terms mod $\displaystyle 5$:

$\displaystyle 2 - 1 + 3 - 4 + 2 - 1$. And we see that the partial sums are $\displaystyle 2, 1, 4, 0$. Bingo, as long as there's a 0 in this sequence then $\displaystyle 5$ divides one of the partial sums.

I'll leave this for now, I'm sure there's a clever little proof in here. Also note that if $\displaystyle n = 2^k$ we're done, because $\displaystyle 2^k$ divides $\displaystyle 2^{2^k}$.
Thanks from mobel

Last edited by Maschke; July 31st, 2015 at 04:40 PM.
Maschke is offline  
August 1st, 2015, 02:52 AM   #3
Banned Camp
 
Joined: Dec 2013

Posts: 1,117
Thanks: 41

Quote:
Originally Posted by Maschke View Post
To begin, your notation's not very good. Because if I ask you what is $\displaystyle S(3)$, then it's $\displaystyle 2^3 = 8$. But if you started from $\displaystyle n = 5$, then $\displaystyle S(3) = 24$. So $\displaystyle S$ is not a function.

Your procedure does generate a sequence of numbers though, so let's see if we can analyze that.

Given $\displaystyle n$, your sequence is:

$\displaystyle 2^n$

$\displaystyle 2^n - 2^{n-1}$

$\displaystyle 2^n - 2^{n-1} + 2^{n-2}$

$\displaystyle 2^n - 2^{n-1} + 2^{n-2} - 2^{n-3}$

...

(*) $\displaystyle 2^n - 2^{n-1} + 2^{n-2} - 2^{n-3} \dots \pm 1$

If $\displaystyle n$ is odd, then the final term is $\displaystyle +1$; if $\displaystyle n$ is odd, the final term is $\displaystyle -1$.

Do you agree so far? I want to make sure I'm understanding your procedure.

Now, your question is a little confusing. You asked



Your example doesn't match what you wrote. If I pick $\displaystyle n = 47$, you are asking if there is some $\displaystyle k$ for which $\displaystyle 47$ divides $\displaystyle S(k)$. But we've already seen that the expression $\displaystyle S(k)$ is not well-defined. Do you mean one of the members of the sequence generated by $\displaystyle 47$?

If so, I think your question is whether $\displaystyle n$ always divides at least one of the partial sums of expression (*).

Does that sound about right?

(edit) As I look at it, this is an interesting problem in modular arithmetic. Look at the example for $\displaystyle n = 5$. Our (*) series is:

$\displaystyle 2^5 - 2^4 + 2^3 - 2^2 + 2 - 1$.

Now look at the terms mod $\displaystyle 5$:

$\displaystyle 2 - 1 + 3 - 4 + 2 - 1$. And we see that the partial sums are $\displaystyle 2, 1, 4, 0$. Bingo, as long as there's a 0 in this sequence then $\displaystyle 5$ divides one of the partial sums.

I'll leave this for now, I'm sure there's a clever little proof in here. Also note that if $\displaystyle n = 2^k$ we're done, because $\displaystyle 2^k$ divides $\displaystyle 2^{2^k}$.
My procedure was understood in other forums even if they said that my notation was unclear. I had received some proofs yet.
For n=7

S(7)=128
S(6)=64
S(5)=96
S(4)=80
S(3)=88
S(2)=84
S(1)=86
S(0)=85

7 divides S(2) because 84=7*12

It exists at least one value of k such as n divides some S(k)
Is it true?
How to prove it?

Last edited by mobel; August 1st, 2015 at 03:09 AM.
mobel is offline  
August 1st, 2015, 02:14 PM   #4
Senior Member
 
Joined: Aug 2012

Posts: 2,356
Thanks: 738

I wrote a little program and verified this up to n = 10,000. Looking at the problem, I think this must either be very simple or very difficult. It's about how you combine the residues with alternating signs. Why must there be a zero in the alternating sequence of partial sums of the residues, ordered by descending exponent? It's very curious, isn't it?

Writing the program is interesting. Of course this is a very simple program to write, but the performance aspects are fascinating. Computing the residues mod n of the powers of 2^k for k <= n is the key. You can't just simply raise 2 to a huge power then take the residue, the numbers get far too big to deal with without specialized numeric software.

Much more sensible is to compute the residues as you go. But even that turns out to be fairly slow as n gets large. It turns out there is a lot of literature on the subject of algorithms to compute 2^k mod n. It's summarized in these two Wiki articles. I found them interesting.

https://en.wikipedia.org/wiki/Modular_exponentiation

https://en.wikipedia.org/wiki/Expone...on_by_squaring

However I think this problem's going to take some number theory. I don't even have a sense of whether this is an easy or a hard problem.
Maschke is offline  
August 2nd, 2015, 12:17 AM   #5
Member
 
Joined: Oct 2010

Posts: 72
Thanks: 3

Also see number theory - How come $\ n\ $ always divides at least one of the item of the sequence? - Mathematics Stack Exchange
Thanks from mobel
miket is offline  
August 2nd, 2015, 04:09 AM   #6
Banned Camp
 
Joined: Dec 2013

Posts: 1,117
Thanks: 41

Thanks a lot for this elegant proof!
mobel is offline  
August 2nd, 2015, 01:57 PM   #7
Senior Member
 
Joined: Dec 2007

Posts: 687
Thanks: 47

We need only to check $n$ odd, since your conjecture is true for $n$ being powers of 2, for all terms are even but the last one $S(0)=even\pm 1=odd$.

a) $S(n)=2^n=1\cdot 2^{n}$

b) $S(n-1)=2^n-2^{n-1}=1\cdot 2^{n-1}$

c) $S(n-2)=2^{n-1}+2^{n-2}=3\cdot 2^{n-2}$

d) $S(n-3)=3\cdot 2^{n-2}-2^{n-3}=6\cdot 2^{n-3}-2^{n-3}=5\cdot 2^{n-3}$

e) $S(n-4)=5\cdot 2^{n-3}+2^{n-4}=10\cdot 2^{n-4}+2^{n-4}=11\cdot 2^{n-4}$

So the sequence of coefficients $c$ is actually

$$
1,1,3,5,11,\ldots,c,2c\pm 1,\ldots,n
$$

and the question can be restated as whether or not a sequence of length $n$ has an element $c$ multiple of $n$. Lets call it a Mobel sequence.

Notice that we can check whether or not any Mobel sequence of prime length $p$ has a term divisible by $p$, since in this case a positive answer makes the general question follow immediately.

Let $n=p$, and assume $c_i, 2c_i-1, 2^2c_i-1, 2^3c_i-3, 2^4c_i-5, 2^5c_i-11, \ldots, 2^{\frac{p-1}{2}}c_i-c_j$ are $\frac{p+1}{2}$ consecutive coefficients in the Mobel sequence where none is divisible by $p$. Notice that the negatives are again the sequence up to the $\textstyle\frac{p-1}{2}-th$ value, then

$$
c_i, 2c_i-c_1, 2^2c_i-c_2, 2^3c_i-c_3, 2^4c_i-c_4, 2^5c_i-c_5, \ldots, 2^{\frac{p-1}{2}}c_i-c_{\frac{p-1}{2}}
$$

In particular,

$$
2^{\frac{p-1}{2}}c_i\not\equiv c_\frac{p-1}{2}\pmod p\Rightarrow 2^{p-1}c_i^2\not\equiv c_\frac{p-1}{2}^2\pmod p\Rightarrow c_i^2\not\equiv c_\frac{p-1}{2}^2\pmod p
$$

Since the length of such list of consecutive coefficients is $\frac{p+1}{2}$, and there are $p+1$ terms in the Mobel sequence, then we have $i\in\{1,2,\ldots,\frac{p-1}{2}\}$.

This means that
$$
\begin{array}{ll}

c_1^2&\not\equiv c_\frac{p-1}{2}^2\pmod p\\
c_2^2&\not\equiv c_\frac{p-1}{2}^2\pmod p\\
&\vdots\\
c_\frac{p-1}{2}^2&\not\equiv c_\frac{p-1}{2}^2\pmod p

\end{array}
$$

The last equivalence is absurd, thus $p$ divides at least one term of the Mobel sequence. $\blacksquare$
Thanks from mobel
al-mahed is offline  
August 2nd, 2015, 02:20 PM   #8
Senior Member
 
Joined: Dec 2007

Posts: 687
Thanks: 47

Just a minor, where I say "sequence of length n" it should read "sequence of length $n+1$". Also, the list is written $1,1,3,5,11,\ldots,c,2c\pm 1,\ldots,n$ but should be written $1,1,3,5,11,\ldots,c_i,2c_i\pm 1,\ldots,c_{n+1}$.
al-mahed is offline  
August 3rd, 2015, 04:50 AM   #9
Banned Camp
 
Joined: Dec 2013

Posts: 1,117
Thanks: 41

In fact it will work with any a^n (a>=2).
mobel is offline  
August 3rd, 2015, 08:45 AM   #10
Senior Member
 
Joined: Dec 2007

Posts: 687
Thanks: 47

Quote:
Originally Posted by mobel View Post
In fact it will work with any a^n (a>=2).
So your new claim is that any sequence of length $p+1$, generated by the rules:

\begin{array}{lll}
a) &S_p&=a^p\\
b) &S_{p-1}&=S_p-a^{p-1}\\
&\vdots&\\
c) &S_{0}&=S_1-a^{0}
\end{array}

has at least one term $S_i$ such that $p\mid S_i$ for all $a>1$?
al-mahed is offline  
Reply

  My Math Forum > College Math Forum > Number Theory

Tags
conjecture



Thread Tools
Display Modes


Similar Threads
Thread Thread Starter Forum Replies Last Post
Conjecture about primitive roots of "prime" cyclic groups Sebastian Garth Number Theory 6 October 25th, 2013 07:21 PM
A "simple" application of dirac delta "shift theorem"...help SedaKhold Calculus 0 February 13th, 2012 11:45 AM
Conjecture on "proof on proofs" for infinite cases Eureka Number Theory 6 January 29th, 2012 02:28 AM
"separate and integrate" or "Orangutang method" The Chaz Calculus 1 August 5th, 2011 09:03 PM
sample exeriment-need help finding "statistic" and "result" katie0127 Advanced Statistics 0 December 3rd, 2008 01:54 PM





Copyright © 2019 My Math Forum. All rights reserved.