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(n1)=S(n)(2^n1) S(n2)=S(n1)+(2^n2) S(n3)=S(n2)(2^n3) .... 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^52^4=3216=16 S(3)=16+2^3=24 S(2)=242^2=20 S(1)=20+2=22 S(0)=22(2^0)=221=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 counterexample? Can we prove the conjecture? Thank you. 
July 31st, 2015, 04:11 PM  #2  
Senior Member Joined: Aug 2012 Posts: 2,356 Thanks: 738  Quote:
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^{n1}$ $\displaystyle 2^n  2^{n1} + 2^{n2}$ $\displaystyle 2^n  2^{n1} + 2^{n2}  2^{n3}$ ... (*) $\displaystyle 2^n  2^{n1} + 2^{n2}  2^{n3} \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:
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}$. Last edited by Maschke; July 31st, 2015 at 04:40 PM.  
August 1st, 2015, 02:52 AM  #3  
Banned Camp Joined: Dec 2013 Posts: 1,117 Thanks: 41  Quote:
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.  
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. 
August 2nd, 2015, 12:17 AM  #5 
Member Joined: Oct 2010 Posts: 72 Thanks: 3  
August 2nd, 2015, 04:09 AM  #6  
Banned Camp Joined: Dec 2013 Posts: 1,117 Thanks: 41  Quote:  
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(n1)=2^n2^{n1}=1\cdot 2^{n1}$ c) $S(n2)=2^{n1}+2^{n2}=3\cdot 2^{n2}$ d) $S(n3)=3\cdot 2^{n2}2^{n3}=6\cdot 2^{n3}2^{n3}=5\cdot 2^{n3}$ e) $S(n4)=5\cdot 2^{n3}+2^{n4}=10\cdot 2^{n4}+2^{n4}=11\cdot 2^{n4}$ 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_i1, 2^2c_i1, 2^3c_i3, 2^4c_i5, 2^5c_i11, \ldots, 2^{\frac{p1}{2}}c_ic_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{p1}{2}th$ value, then $$ c_i, 2c_ic_1, 2^2c_ic_2, 2^3c_ic_3, 2^4c_ic_4, 2^5c_ic_5, \ldots, 2^{\frac{p1}{2}}c_ic_{\frac{p1}{2}} $$ In particular, $$ 2^{\frac{p1}{2}}c_i\not\equiv c_\frac{p1}{2}\pmod p\Rightarrow 2^{p1}c_i^2\not\equiv c_\frac{p1}{2}^2\pmod p\Rightarrow c_i^2\not\equiv c_\frac{p1}{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{p1}{2}\}$. This means that $$ \begin{array}{ll} c_1^2&\not\equiv c_\frac{p1}{2}^2\pmod p\\ c_2^2&\not\equiv c_\frac{p1}{2}^2\pmod p\\ &\vdots\\ c_\frac{p1}{2}^2&\not\equiv c_\frac{p1}{2}^2\pmod p \end{array} $$ The last equivalence is absurd, thus $p$ divides at least one term of the Mobel sequence. $\blacksquare$ 
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}$.

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

August 3rd, 2015, 08:45 AM  #10 
Senior Member Joined: Dec 2007 Posts: 687 Thanks: 47  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_{p1}&=S_pa^{p1}\\ &\vdots&\\ c) &S_{0}&=S_1a^{0} \end{array} has at least one term $S_i$ such that $p\mid S_i$ for all $a>1$? 

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 exerimentneed help finding "statistic" and "result"  katie0127  Advanced Statistics  0  December 3rd, 2008 01:54 PM 