User Name Remember Me? Password

 Number Theory Number Theory Math Forum

 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. July 31st, 2015, 04:11 PM   #2
Senior Member

Joined: Aug 2012

Posts: 2,356
Thanks: 738

Quote:
 Originally Posted by mobel 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 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}$.

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:
 Originally Posted by Maschke 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. 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 Thanks from mobel August 2nd, 2015, 04:09 AM #6 Banned Camp   Joined: Dec 2013 Posts: 1,117 Thanks: 41 Thanks a lot for this elegant proof! 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 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

Quote:
 Originally Posted by mobel 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$? Tags conjecture Thread Tools Show Printable Version Email this Page Display Modes Linear Mode Switch to Hybrid Mode Switch to Threaded Mode Similar Threads Thread Thread Starter Forum Replies Last Post Sebastian Garth Number Theory 6 October 25th, 2013 07:21 PM SedaKhold Calculus 0 February 13th, 2012 11:45 AM Eureka Number Theory 6 January 29th, 2012 02:28 AM The Chaz Calculus 1 August 5th, 2011 09:03 PM katie0127 Advanced Statistics 0 December 3rd, 2008 01:54 PM

 Contact - Home - Forums - Cryptocurrency Forum - Top

Copyright © 2019 My Math Forum. All rights reserved.      