Player (36)
Joined: 9/11/2004
Posts: 2630
This evening I looked into the Erdos conjecture on arithmetic progressions and attempted to prove the contrapositive by attempting to place an upper bound on series with various progression lengths. So here's a few challenges that arose out of that. 1. Given the following series: 1/1+1/1+1/2+1/2+1/4+1/4+1/5+1/5+1/10+1/10+1/11+1/11+1/13+1/13+1/14+1/14+1/28+1/28+1/29+1/29+1/31+1/31+1/32+1/32+1/37+1/37+1/38+1/38+1/40+1/40+1/41+1/41+1/82+1/82+ ... (Why doubled? Because arithmetic progressions of common difference 0 count too.) Prove this that series converges to the highest possible value that any series of whole number reciprocals can without containing an arithmetic progression with a length greater than 2. (When I say length greater than n I mean the arithmetic progression does not contain more than n members.) 2. What is the series of whole number reciprocals that do not contain an arithmetic progression with a length greater than 3 that converges to the highest possible value? 3. It seems that some of these series have regular, patterned and self symmetric behavior and others have quite chaotic behavior, any clue as to how to predict this?
Build a man a fire, warm him for a day, Set a man on fire, warm him for the rest of his life.
Joined: 7/16/2006
Posts: 635
To OmnipotentEntity: 1 and 2) I haven't proven that this is maximal, but it seems like it is. I shall ignore arithmetic progressions with common difference 0, as they aren't really important to the problem. If we wish to find a sequence that contains no arithmetic sequence longer than n, then the algorithm is as follows. Start with a sequence S={1,2,...,n}. Now, starting with N=n+1, see if N makes an arithmetic sequence of length n+1 when combined with the sequence S. If no, add N to S. Then move on to N+1 and repeat. Using this algorithm, I came up with this sequence for part 2 (terms less than 100 shown). 1 2 3 5 6 8 9 10 15 16 17 19 26 27 29 30 31 34 37 49 50 51 53 54 56 57 58 63 65 66 67 80 87 88 89 91 94 99... I'll get to part 3 later. However, an interesting thing is that the sum in part 1 seems to sum to 3 (again, ignoring common differences of 0). Does it really sum to 3? Is there a simple relation between the sum of the series and n?
Player (36)
Joined: 9/11/2004
Posts: 2630
Ignoring arithmetic progressions of 0. The even progression lengths behave regularly, and the odds... don't. The even ones seem to converge up to n+1 where n is the progression length. The odd numbers.... don't. I've wrote a program to generate arithmetic progressions the same way that you described. (Proving it generates the densest set is a different matter, of course.) And I let it run over night. For progression length 2, it's converged very quickly on 3. For progression length 3, it is converging very very slowly on a number at least 4.2623
23741011 241957   125 4.262390641893804677
23741094 241958    83 4.2623906840148624298
23741153 241959    59 4.2623907261358162657
23741480 241960   327 4.2623907682561892329
23741530 241961    50 4.2623908103764733823
23741690 241962   160 4.2623908524964742028
23741798 241963   108 4.2623908946162831768
23741883 241964    85 4.2623909367359411604
23741980 241965    97 4.2623909788554277256
23742158 241966   178 4.2623910209745980993
I just tailed the results and that's what I get, the columns are current member of the series, current series length, difference between the current member and the last member, and the sum total. I haven't a clue when it's going to stabilize out. If anyone cares to run it on a faster computer, here's the code I wrote, it's a little hackish, but well optimized.
#include <iostream>
#include <iomanip>

int main() {
  int series[1000000]; //we can change this later if we need more computingness.
  series[0] = 1;
  int series_length = 1;
  int length_arith_prog = 3;
  double sum = 1.0;
  int n = 2;
  std::cout << std::setprecision(20);

  for (;;n++) {
    int found = 0;
    for (int i=0; i < series_length && found == 0; i++) {
      int members_arith_prog = 0;
      int debug = (n - series[i])%length_arith_prog;
      if (!((n - series[i])%length_arith_prog)) { //if between these two numbers it is possible to have an arithmetic progression of the specified length
        int common_diff = (n - series[i])/length_arith_prog;
        for (int j=1; j < length_arith_prog; j++) {
/*          for (int k=i+1; k < series_length; k++) { //we only want to test numbers larger than the one we're currently examining.
            if (series[k] == series[i] + j*common_diff) {
              members_arith_prog++;
            }
          }*/
          int mid=((i+1)+(series_length-1))/2; //the +1 and -1 cancel, they're just there to remind me.
          int high = series_length;
          int low = i+1;
          int value = series[i] + j*common_diff;
          while (low < high) {
            mid = low + ((high - low) / 2);  // Note: not (low + high) / 2 !!
            if (series[mid] < value) {
              low = mid + 1;
            } else {
              high = mid;
            }
          }
          if ((low < series_length) && (series[low] == value)) {
            members_arith_prog++;
          }
        }
      }

      if (members_arith_prog+1 == length_arith_prog) { //found a arithmetic progression!
        found = 1;
      }
    }
    if (found == 0) {
      series[series_length] = n;
      int deriv = series[series_length] - series[series_length-1];
      series_length++;
      sum += (1.0/n);
      std::cout << n << " " << series_length << " " << std::setw(5) << deriv << " " << sum << std::endl;
    }

  }
}
Build a man a fire, warm him for a day, Set a man on fire, warm him for the rest of his life.
Player (36)
Joined: 9/11/2004
Posts: 2630
Actually with a max progression length, it doesn't converge on 3, it's slightly larger than 3. :/ Well, so much for pretty numbers.
Build a man a fire, warm him for a day, Set a man on fire, warm him for the rest of his life.
Joined: 7/16/2006
Posts: 635
Heh, I actually wrote my code for my TI-89 to generate my answers. It was rather slow, probably due to the 89's bad processor and inefficiencies in the code, but it worked well for generating the series up to 100. This is what I used.
tasg(n,m)
Func
Local s
Local i
Local j
Local k
{1,2,...,n}->s
For i, n+1, m
    For j, 1, i/n
        For k, 1, n
            If product(i-k*j-s) =/= 0
            goto Y
        EndFor
        Goto N
        Lbl Y
    EndFor
    {s,i}->s
    Lbl N
EndFor
s
EndFunc
{s,i} and {1,2,...n} are not the exact TI-89 commands, due to the fact that the TI-89 inexplicably has no list-joining command. But it is their effect. The actual commands are mat>list(augment(list>mat(s),[])) and cumSum(mat>list(diag(identity(n)))). The TI-89 language is pretty easy to understand, so you should be able to work out what it does. I'd try running your code, but I'm not sure what language it's in, nor what I'd need to run it. EDIT: Not exactly 3, eh? Well, that's strange. Are we certain it converges? It seems like it should, but still.
Player (36)
Joined: 9/11/2004
Posts: 2630
Some findings, The algorithm seems imperfect for progression lengths that have chaotic behavior. These are generally odd values; however, values of 8 and 14 also exhibit this behavior. (Only have tested values up to 18.) This is what I have thus far plotted against the harmonic series. From the bottom up are all of the well behaved progression values (chaotic ones sum up to less than expected, and therefore the algorithm used to generate them is flawed.) We are probably dealing with the difference between divergent and convergent series, so it's unsurprising how slowly everything seems to converge. I kinda want to try, just for kicks, a very large progression value and plot it against the harmonic series, when I'm done with these current jobs. From bottom, 2, 4, 6, 10, 12, 16, 18, harmonic I'm currently running these until they reach 1 million terms. Here's some numerical results.
==> results-k2.txt <==
48626849 90110     1 3.0047502371298553392
48626851 90111     2 3.0047502576946252262
48626852 90112     1 3.0047502782593946691

==> results-k4.txt <==
3417967 524286     1 6.9855757435193490679
3417968 524287     1 6.9855760360908414341
3417969 524288     1 6.9855763286622485353

==> results-k6.txt <==
2323521 834442     1 9.4759921775889957019
2323522 834443     1 9.4759926079701148893
2323523 834444     1 9.4759930383510493357

==> results-k10.txt <==
1395678 873659     1 11.675478284103704141
1395679 873660     1 11.675479000600835988
1395681 873661     2 11.675479717096941101

==> results-k12.txt <==
461429 314551     1 11.501411429098064687
461430 314552     1 11.501413596274018047
461431 314553     1 11.50141576344527472

==> results-k16.txt <==
404982 321368     1 12.059011402079701014
404983 321369     1 12.059013871319150368
404984 321370     1 12.059016340552503266

==> results-k18.txt <==
391782 315668     1 12.218301410935204387
391783 315669     1 12.218303963368565945
391784 315670     1 12.218306515795413603
Build a man a fire, warm him for a day, Set a man on fire, warm him for the rest of his life.
Player (36)
Joined: 9/11/2004
Posts: 2630
petrie911 wrote:
I'd try running your code, but I'm not sure what language it's in, nor what I'd need to run it.
It's in C++, you'll need to compile it to run. http://gcc.gnu.org/
Build a man a fire, warm him for a day, Set a man on fire, warm him for the rest of his life.
arflech
He/Him
Joined: 5/3/2008
Posts: 1120
If you're using Windows, go here to get GCC: http://www.mingw.org/ You can also download free environments like Code::Blocks that include their own local MinGW distributions. Another option for Windows users is to get Visual C++ Express 2008: http://www.microsoft.com/express/product/ If for some reason you want Visual Studio 2005 Express editions, which were completely obsoleted by VS2008, go here: http://webkoleji.net/visual/ If you're using a Mac, try this: http://www.finkproject.org/ or this: http://www.macports.org/ OS X comes with GCC, but I heard Apple's build of GCC is broken
i imgur com/QiCaaH8 png
Banned User
Joined: 3/10/2004
Posts: 7698
Location: Finland
I have the need for this algorithm in practice. Suppose you have the rotation notation <angle1, angle2, angle3>. That means: "First rotate around the X axis by angle1 degrees, then around the Y axis by angle2 degrees, and finally around the Z axis by angle3 degrees." Also assume that you can apply any amount of such rotations in succession. For example, you could first apply the rotation <0, 35, 60>, then <15, -50, 0> and then <-5, 0, 20>. It is, in fact, possible to create from any amount of such successive rotations one single <angle1, angle2, angle3> triplet which produces the exact same transformation as all those successive rotations. In other words, any amount of successive rotation triplets can be collapsed into one. However, I don't know how this is done.
arflech
He/Him
Joined: 5/3/2008
Posts: 1120
Following this development, represent a rotation in a1 about the x-axis by Rx(a1)=cos(a1/2)+isin(a1/2), in a2 about the y-axis by Ry(a2)=cos(a2/2)+jsin(a2/2), and in a3 about the z-axis by Rz(a3)=cos(a3/2)+ksin(a3/2) (the rotation of p=(p1,p2,p3) represented by P=p1i+p2j+p3k in angle t about the unit vector u is qPq^-1 where q=cos(t/2)+usin(t/2)); then <a1>=Rz(a3)Ry(a2)Rx(a1)=cos(a1/2)cos(a2/2)cos(a3/2)+sin(a1/2)sin(a2/2)sin(a3/2)+(sin(a1/2)cos(a2/2)cos(a3/2)-cos(a1/2)sin(a2/2)sin(a3/2))i+(cos(a1/2)sin(a2/2)cos(a3/2)+sin(a1/2)cos(a2/2)sin(a3/2))j+(cos(a1/2)cos(a2/2)sin(a3/2)-sin(a1/2)sin(a2/2)cos(a3/2))z (I tried this with matrices and it was even more unwieldy). Now all you need is to find an angle t such that cos(t/2)=cos(a1/2)cos(a2/2)cos(a3/2)+sin(a1/2)sin(a2/2)sin(a3/2) and that there exists a unit vector u for which usin(t/2) expands to all of those other terms... It's odd, like it's known that the set of rotations about the origin in 3D is a group known as SO(3), but it's not so easy to make even this simple case explicit. Perhaps this article might work also (I guess there's no analytical formulation and it has to be done numerically): http://www.cgafaq.info/wiki/Euler_angles_from_matrix
i imgur com/QiCaaH8 png
Experienced player (622)
Joined: 11/30/2008
Posts: 650
Location: a little city in the middle of nowhere
I would assume the simplest say do do this problem would be something like this. And by that I mean your original number ^(some quaternion)
Measure once. Cut twice.
Joined: 7/16/2006
Posts: 635
Warp wrote:
I have the need for this algorithm in practice. Suppose you have the rotation notation <angle1>. That means: "First rotate around the X axis by angle1 degrees, then around the Y axis by angle2 degrees, and finally around the Z axis by angle3 degrees." Also assume that you can apply any amount of such rotations in succession. For example, you could first apply the rotation <0>, then <15> and then <5>. It is, in fact, possible to create from any amount of such successive rotations one single <angle1> triplet which produces the exact same transformation as all those successive rotations. In other words, any amount of successive rotation triplets can be collapsed into one. However, I don't know how this is done.
Well, each rotation can be expressed in the form of a 3x3 matrix. Although the exact form depends on the convention you're using for the axes of rotation, an explicit formula for changing angles into matrices can be found. In order to combine rotations, you multiply the matrices together. Then just apply the formula from before in reverse to the resulting matrix.
Joined: 7/4/2009
Posts: 5
How bout we solve for Pi xD
Banned User
Joined: 3/10/2004
Posts: 7698
Location: Finland
Assume two people, person A and person B, who want to decide who gets a price by tossing a coin. Person A is a bad loser and a bully, so if he loses he says "I said it's two out of three". So they play it like that. If A loses again, he says "I said it's three out of five", and so on, until he wins. How many tosses is this game expected to last, in average?
adelikat
He/Him
Emulator Coder, Site Developer, Site Owner, Expert player (3570)
Joined: 11/3/2004
Posts: 4754
Location: Tennessee
Half the time it will last 1 round. So would that not be the expected number of rounds?
It's hard to look this good. My TAS projects
Banned User
Joined: 3/10/2004
Posts: 7698
Location: Finland
adelikat wrote:
Half the time it will last 1 round. So would that not be the expected number of rounds?
No. For the average number of tosses to be 1, either all games must end in one toss, or if there are some games with more than 1 toss there would have to be an equivalent amount of games with "less" than 1 toss to compensate. After all, the average is the sum of tosses in each game divided by the total number of games.
Skilled player (1826)
Joined: 4/20/2005
Posts: 2161
Location: Norrköping, Sweden
Is it 10/9 (i.e. 1.11) tosses? EDIT: Nevermind, that's not right at all. I'll think some more about this. EDIT2: Hmm, on second thought, perhaps it is right. Is it?
Player (121)
Joined: 2/11/2007
Posts: 1522
Infinite? That doesn't really sit well with me but here's my logic (not a proof). Suppose there is a new rule: after n rounds the bully will get mad and declare himself the winner anyways regardless of coin tosses. Obviously a lower n will result in a lower average number of rounds. I wrote a little python script to take the average of 10,000 games, and here are the results:
n          avg
100        15
1000       50
10000      150
100000     515
1000000    1270
10000000   5016
The average roughly correlates with 1.5*sqrt(n). That implies that (as in the original question) if n approaches infinity, so does the average. Quite different than my original guess of about 2 or 3 :) I'd be very interested to see a more rigorous solution.
I make a comic with no image files and you should read it. While there is a lower class, I am in it, and while there is a criminal element I am of it, and while there is a soul in prison, I am not free. -Eugene Debs
Joined: 7/2/2007
Posts: 3960
Usually my first impulse with this kind of problem is to whip up a quick Monte Carlo simulator to see how the numbers behave. So I wrote this:
#!/usr/bin/python
import random

totalRolls = 0
for i in xrange(0, 1000):
    if i % 10 == 0:
        print i
    aCount = 0
    bCount = 0
    numRolls = 0
    curBase = 1
    while numRolls == 0 or bCount < curBase:
        if random.random() > .5: 
            aCount += 1
            if aCount == curBase:
                curBase += 2
        else:   
            bCount += 1
        numRolls += 1
    totalRolls += numRolls
print totalRolls / 1000.0
and then sent it off...and it hung around 970, generating increasingly massive numbers of rolls as the bully became horribly unlucky for a spell. Then I reran it and it finished nigh-instantly with an answer of 497.885. And reran it again and got 2910.299, and so on. I don't think this problem is amenable to Monte Carlo approaches. :) Edit: turned off HTML so it wouldn't mangle my less-than and greater-than signs.
Pyrel - an open-source rewrite of the Angband roguelike game in Python.
Player (121)
Joined: 2/11/2007
Posts: 1522
Heh, that's why I initially capped off the number of tries before "giving up". Here's my code, for what it's worth:
import random
Total = 0
Highest = 0
for i in range(1,10000):
    Heads = 0
    Tails = 0
    Rounds = 0
    while Heads <= Tails and Rounds<100000000:
        Rounds += 1
        if random.randint(0,1) == 1:
            Heads += 1
        else:
            Tails += 1
    Total += Rounds
    if Rounds > Highest:
        Highest = Rounds
    print i
    print Rounds
    print Total/i
print Total/10000.0
print Highest
I make a comic with no image files and you should read it. While there is a lower class, I am in it, and while there is a criminal element I am of it, and while there is a soul in prison, I am not free. -Eugene Debs
Joined: 4/7/2008
Posts: 117
<snip> (I understood the problem incorrectly)
snorlax
He/Him
Joined: 5/20/2007
Posts: 174
Location: Wisconsin
.5+2(.5)^2+3(.5)^3+4(.5)^4+...=SUM(1,INF,x(.5)^x) I had to find a formula for summing this (arithmetic geometric series): For an infinte series a + (a+d)r + (a+2d)r^2 + (a+3d)r^3... S=a/(1-r)+dr/(1-r)^2 a=0 d=1 r=.5 So S=2
Skilled player (1409)
Joined: 5/31/2004
Posts: 1821
snorlax wrote:
.5+2(.5)^2+3(.5)^3+4(.5)^4+...=SUM(1,INF,x(.5)^x) I had to find a formula for summing this (arithmetic geometric series): For an infinte series a + (a+d)r + (a+2d)r^2 + (a+3d)r^3... S=a/(1-r)+dr/(1-r)^2 a=0 d=1 r=.5 So S=2
Ehm... it's not possible for the game to end after two rounds.
adelikat
He/Him
Emulator Coder, Site Developer, Site Owner, Expert player (3570)
Joined: 11/3/2004
Posts: 4754
Location: Tennessee
I find it funny that the guesses so far have ranged from 1 to infinity ^_^
It's hard to look this good. My TAS projects
Joined: 10/20/2006
Posts: 1248
It seems like there's a 1/2 chance that it lasts one round, a 1/8 chance, that it lasts three rounds and a 1/16 chance that it lasts five rounds. 5/128 that it lasts eight rounds. 1/32 that it lasts nine rounds. o_o This is weird. I really don't get the system behind this. On average it could be that it lasts infinite rounds because even if there's a 99% that it lasts 1 round and 1% that it lasts for infinite rounds, the average is infinite rounds. (1*infinity+99*1)/100. If the chance to get infinite rounds is infinitely low, that's another thing. I'm not sure if that's the case here. The chance that it lasts for infinite times is lower 25% at least. Should be even lower. I'd say calculating the probability that it lasts for an infinite amount of times would be interesting, but I'm not able to do it. Probability to end at: Best of one: 1/2 Best of three: (1 - BO1 winning probability) * 1/2 (to get even then) * 1/2 (to win after that) Best of five: (1 - BO1 winning probability - BO3 winning probability) * (probability to get even) * 1/2 Probability to get even - for 0-3, for 1-3, for 2-3 => probability to get into that situation * probability to get even in that situation => 1/(2 to the power of 3) * 1/(2 to the power of 3) + 1/(2 to the power of 4) * 1/(2 to the power of 2) + 1/(2 to the power of 5) * 1/(2 to the power of 1) Best of seven: (1 - BO1 winning probability - BO3 winning probability - BO5 winning probability) * probability to get even * 1/2 Probability to get even - for 0-5, 1-5, 2-5, 3-5, 4-5 => 1/(2 power 5) * 1/(2 power 5) + 1/(2 power 6) * 1/(2 power 4) + 1/(2 power 7) * 1/(2 power 3) + 1/(2 power 8) * 1/(2 power 2) + 1/(2 power 9) * 1/(2 power 1) Probability to get even for best of X: a = 1, b = 2X - 1, c = 0 do c += 1/(2 power a) * 1/(2 power b) a++; b--; until a > b Probability to end at best of X: a = X; b = 1; while not a == 1 a -= 2 b -= Probability to end at best of a continue c = b * Probability to get even for best of X * 1/2 Probability to end the game at all = Probability to end at best of "lowest uneven number smaller than infinity" lol, I don't get it (yet?). You'd probably have to turn my stuff into a formula and use a limes or whatever it's called. That is if I haven't screwed up. I suck at the language of math, so I can't write down a formula for it. xD I hope I didn't make any huge mistakes. It could be I've made one, I'm too lazy to think through the whole thing a second time though. :P

1731100097