Shlomi Fish avatar Shlomi Fish committed 8766631

Add the #122 planning document.

Comments (0)

Files changed (2)

project-euler/122/122-planning.txt

+1: 1 -> 0
+
+2: 1+1 -> 1
+
+3: 2+1 -> 2
+
+4: 2+2 -> 2
+
+5: 2+3 -> 3 ; 4+1 -> 3 ; ---> 3
+
+6: 3+3 -> 3 ; 4+2 -> 3 ; 1+5 -> 4
+
+7: 1,2,3,4,7 -> 4 ; 1,2,3,6,7 -> 4
+
+8: 1,2,4,8 -> 3
+
+9: 1,2,4,8,9 -> 4 ; 1,2,3,6,9 -> 4 ; 1,2,4,5,9 -> 4
+
+10: 1,2,4,5,10 -> 4
+
+11: 1,2,4,8,10,11 -> 5 ; 1,2,3,6,9,11 -> 5 ; 1,2,4,5,10,11 -> 5 ; 
+    1,2,4,5,6,11 -> 5
+
+12: 1,2,3,6,12 -> 4 ; 1,2,4,8,12 -> 4 [3 * 2 * 2]
+
+13: 1,2,4,8,12,13 -> 5 ; 1,2,3,6,12,13 -> 5
+
+14: 7*2 -> 5 ; 1,2,4,8,12,14 -> 5
+
+15: 1,2,3,6,9,15 -> 5 ; 1,2,3,5,10,15 -> 5
+
+16: 1,2,4,8,16 -> 4
+
+17: 1,2,4,8,16,17 -> 5
+
+
+
+
+
+
+
+
+
+Lemma 1:
+--------
+
+rank(2*x+1) >= rank(2*x).
+
+Proof: let's assume that x is the minimal natural number for which 
+rank(2*x+1) < rank(2*x). If its best composition was "(2*x)+(1)" then
+2*x would have a lower rank. Therefore it is i+j. Now since 2*x+1 is odd,
+it means one of i,j is even and the other odd. Without loss of generality,
+let's assume that i is even and j is odd.
+
+Let's look at the composition C[2*x+1] at one point we add 1 to an even number
+Let's not add it there. If we can still form 2*x with the lower rank then we 
+have a contradiction. If, OTOH, we do something with [2*a'+1], like add it to
+another number then either:
+
+1. Instead of doing [2*a'+1]+[2*b'+1] we can do [2*a']+[2*b']+2  to get the
+same sum with the same, or lesser, effort.
+
+2. If we multiply [2*a'+1] by two to get [2*a'+1]*2, we can do 
+[2*a']*2+2 and get it at the same effort.
+
+Therefore, the rank of 2*x+1 must be greater or equal to that of 2*x.
+
+Q.E.D.
+
+Lemma 2:
+--------
+
+For every x \in N : rank(2*x) == rank(x)+1 and its best composition is that of 
+x+x. 
+
+Proof: let's call r = rank(x). So in order to beat the "x+x" composition,
+we need to find two integers, i and j <> x, so that i+j=x+x and
+rank(i)+rank(j)-rank(i /\ j) <= r-1 . Now, if i and j are both even,
+the we can take the "i/2+j/2" composition to find a better composition for
+x, and so yield a lower r (which is reductio ad absurdum). Therefore, i
+and j are both odd (because an odd number plus an even number cannot be
+2*x). 
+
+Let's assume that i < j (if i=j then i=j=x). If i = 1 then according to
+Lemma 1 then rank(j-1) <= rank(j) and we can use "(j-1)+(2)" instead
+to yield a minimal sum which is a contradiction.
+
+So i >= 3. 
+
+Let's look at "(i-1)+(j-1)" 
+Now since rank(i-1) <= rank(i) and rank(j-1) <= rank(j)
+Now, in order to form an odd number one has to add 1 to an even power
+of 2 such as 2, 4, 8, 16, etc (which clearly are minimally composed). 
+If 
+
+Removed:
+--------
+
+If C[2*x+1] (where C is the composition) is {1,2,.....a2,a1, 2*x+1}
+then a2 != a1 or else 2*x+1 will be odd. So a1 > x. Now, let's take the 
+identical set only with a1-1 - {1,2,.....a2,a1-1,2*x} . We need to compose
+a1-1 somehow and make sure that (2*x+1-a1) is still a composing number.
+
+a1 = a[n] + a[m] -> a1-1 = a[n] + a[m]-1.
+
+
+Let's take "(i)+(j-1)". Since j-1 < 2*x, then rank(j-1) <= rank(j). So
+rank(i) + rank(j-1) <= rank(i) + rank(j) . But it is possible i and j
+have some common components. Let's mark these components as {a1,a2,a3,a4}
+It is clear that a1 is 1 and a2 = 2, because these start all compositions.
+
+i = {1,2....i}
+j = {1,2....j}
+j-1 = {1,2....j-1}
+
+Since j-1 < j then the number of elements in the j-1 set is lesser or
+equal to that of j. 
+

project-euler/122/euler-122-take2.pl

 }
 
 my $sum = 0;
+print "1: 0\n";
+
 foreach my $n (2 .. 200)
 {
-    print "Reached $n\n";
+    # print "Reached $n\n";
     my $sets = [];
 
     foreach my $lower (1 .. ($n>>1))
         map { unpack("b*", $_) =~ tr/1/1/ } @{$combinations[$n]}
     );
 
-    print "Found $result\n";
+    print "${n}: $result\n";
 
     $sum += $result;
 }
Tip: Filter by directory path e.g. /media app.js to search for public/media/app.js.
Tip: Use camelCasing e.g. ProjME to search for ProjectModifiedEvent.java.
Tip: Filter by extension type e.g. /repo .js to search for all .js files in the /repo directory.
Tip: Separate your search with spaces e.g. /ssh pom.xml to search for src/ssh/pom.xml.
Tip: Use ↑ and ↓ arrow keys to navigate and return to view the file.
Tip: You can also navigate files with Ctrl+j (next) and Ctrl+k (previous) and view the file with Ctrl+o.
Tip: You can also navigate files with Alt+j (next) and Alt+k (previous) and view the file with Alt+o.