Commits

Shlomi Fish committed 489f853

Add more to the planning.

Comments (0)

Files changed (2)

project-euler/122/122-planning.txt

 
 17: 1,2,4,8,16,17 -> 5
 
-
+23: 1,2,4,8,16,20,22,23 -> 7 ; 1,2,3,5,10,20,23 -> 6
 
 
 
 Lemma 2:
 --------
 
-For every x \in N : rank(2*x) == rank(x)+1 and its best composition is that of 
-x+x. 
+For every x \in N : rank(2*x) == rank(x)+1 and one of its best compositions is 
+that of "(x)+(x)".
 
-Proof: let's call r = rank(x). So in order to beat the "x+x" composition,
+Proof: let's assume it is true for all y \in {1 .. x-1} and show it is also
+true for x.
+
+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
 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.
+Let's assume that i < j (if i=j then i=j=x). Since j-1 >= x then 
+rank(j) >= rank(j-1) >= log_2[j-1] >= log_2[x] (according to Lemma 1 and the 
+induction assumption). So j+i will be at least rank(j)+1 which won't be better
+than rank(x)+1 (why? - left as an exercise for the future).
 
-So i >= 3. 
+Lemma 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 
+It's impossible to have @ranks = [... r , r-1 , r-1,] - it must be [ r, r-1, r].
+
+Proof 3:
+--------
+
+Since ranks[x+1] = r-1 < ranks[x] = r then (x + 1) mod 2 == 0 or else
+it will be impossible according to lemma . 
+
+If ranks[x+2] = r-1 then we can construct a ranks[x] = r-1 in a similar way
+to that in Lemma 1:
+
+1. [x+2] = {1,2,....i,j}
+
+2. [x] = {1,2....i,j-2}
+
+
+
+
+
+
+
+
+
+
+
 
 Removed:
 --------
 Since j-1 < j then the number of elements in the j-1 set is lesser or
 equal to that of j. 
 
+Removed 2:
+----------
+
+,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 
+

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

 
 use List::MoreUtils qw(uniq);
 use List::Util qw(min);
+use List::UtilsBy qw(min_by);
+use IO::Handle;
+
+STDOUT->autoflush(1);
 
 =head1 DESCRIPTION
 
     # $combinations[$n] = [sort { $a cmp $b } keys(%sets)];
     $combinations[$n] = $sets;
 
-    my $result = -1 + min
-    (
-        map { unpack("b*", $_) =~ tr/1/1/ } @{$combinations[$n]}
-    );
+    my $optimal_comb = min_by { unpack("b*", $_) =~ tr/1/1/ } @{$combinations[$n]};
 
-    print "${n}: $result\n";
+    my $comb = unpack("b*", $optimal_comb);
+    my $result = -1 + $comb =~ tr/1/1/;
+
+    print "${n}: $result ($comb)\n";
 
     $sum += $result;
 }