29
$\begingroup$

Let $a_n=(-1)^{\left\lfloor{\frac{3^n}{2^n}}\right\rfloor}$ and $$s_n=\sum_{k=1}^na_k.$$

Is it true that $s_n\le 0$ for all $n\geq 1$ ? (This is true for $n\le 100000$.)

In other words, odd numbers are always more than even numbers on the sequence $\left\lfloor{\frac{3^n}{2^n}}\right\rfloor$. This is unexpected, I think they should be roughly equal, and even numbers will exceed odd numbers sometimes.

$\endgroup$
18
  • 3
    $\begingroup$ I like the word "odevity", even though it's not English. :-) languagelog.ldc.upenn.edu/nll/?p=42739 The question itself is interesting, I thought the distribution of the fractional parts of $\left(\frac32\right)^n$ was the one we don't know much about... $\endgroup$ – qfwfq Mar 2 at 7:24
  • 2
    $\begingroup$ @preferred_anon If I'm not mistaken it starts $1, 0, 1, 1, 1, 1, 1, 1, 0, 1, 0, 1, 0, 1, 1, \dots$. $\endgroup$ – Ravi Fernando Mar 2 at 7:55
  • 1
    $\begingroup$ Each ratio $a/b$ has its own behavior. There are ratios like $7/5$ that give more evens than odds at least for $n<10000$. Others like $4/3$ start odd-heavy and turn to even-heavy. $\endgroup$ – Chrystomath Mar 2 at 8:04
  • 1
    $\begingroup$ If my numerical testing is correct this is not true for all $n$; the first time where $s_n>0$ is $n=331523$, with $165762$ even and $165761$ odd numbers $\endgroup$ – hgmath Mar 2 at 13:32
  • 1
    $\begingroup$ @qfwfq I think the integer part of $\left(\frac{3}{2}\right)^n$ is even iff the fractional part of $\frac{1}{2}\left(\frac{3}{2}\right)^n$ is less than $\frac{1}{2}$, so it would still be somewhat connected to fractional parts... $\endgroup$ – hgmath Mar 2 at 13:39
13
$\begingroup$

Not a complete answer, but here are some results from computer simulation:

While the sequence $s_n$ starts out being negative for quite some time (as mentioned in the question, for more than the first $100\,000$ terms), it does reach positive values eventually. The first time this happens is for $n=331\,523$; there we have $165\,762$ even and $165\,761$ odd numbers. So the answer to the question would be no.

After that it continues to alternate between positive and negative values.

See this plot of $s_n$ for $n$ up to $1\,000\,000$: graph

Here is how it continues up to $5\,000\,000$: graph2

Of course it would be nice if this could be verified without computer help... or to see a theoretical description of the asympotic behavior of $s_n$...

$\endgroup$
7
  • 3
    $\begingroup$ @donaastor this particular sequence is pretty nice for computer calculation because you don't need to divide anything at all (that would by far be the most expensive operation). Instead we can do everything in integer arithmetic. The parity of the integer part of $3^n/2^n$ can be obtained as the (n+1)-th digit in the binary representation of $3^n$ (counting from the right). (Dividing by $2^n$ is right shift by $n$, parity is last digit.) Now we can just iteratively calculate the powers of $3$ (note that multiplying by $3$ is just doubling and adding) and take the appropiate digits $\endgroup$ – hgmath Mar 2 at 16:44
  • 2
    $\begingroup$ Time complexity is quadratic; getting to the first positive $s_n$ takes a few seconds, the first million $n$ about a minute $\endgroup$ – hgmath Mar 2 at 16:46
  • 2
    $\begingroup$ This was exactly what I was asking for. Thank you. I could have thinked of an algorithm like that, but it still surprises me that all that computation can be done in under a minute. Fantastic :) I thought that there might be some trickier method that everybody considered trivial haha $\endgroup$ – donaastor Mar 2 at 17:02
  • 1
    $\begingroup$ @hgmath How do you store a number so large as $3^{1,000,000}$ though? Or do you only compute up to the $n+1$th digit in the binary representation? Any sample code would be really helpful :) $\endgroup$ – acephalous Mar 2 at 21:21
  • 1
    $\begingroup$ @chaos Storing these numbers is really not a problem, since $\log_2(3)<1.6$ the number $3^{1\,000\,000}$ takes less than $1\,600\,000$ bits which is $200$ kilobytes... Of course the arithmetic operations get more expensive with longer numbers $\endgroup$ – hgmath Mar 3 at 20:37

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.