Project Euler #372

[science_man_88]

Originally Posted by science_man_88

doh I seem to be working on a N sided die not a 6 sided one. just shows the importance or THOROUGHLY reading instructions:

(e)->j=0;k=1;a=vector(3,b,vecsort(vector(6,b,d=0;until(d>0,d=random(e+1));d),,4));for(f=1,3,for(g=if(f==1,2,if(f==2,3,if(f==3,1))),if(f==1,2,if(f==2,3,if(f==3,1))),if(a[f]==a[g],next(2));for(h=1,6,for(i=k,6,if(a[f][h]<a[g][i],k=k+1,j=j+k*(e-h)))));if((j/(e^2))>.5,,return(0));j=0;k=1);return(1)

a few changes and a few number changes changing to 6. I'm currently using a second code to check this a bit I just have to figure out how to figure out uniqueness or test an amount that will give the correct answers.

I was just going to eliminate a whole lot of possibilities other than a[f]==a[g], by changing it to vecsort(a[f],,4)==vecsort(a[g],,4) but at times I get a forbidden followed by a unknown type 48 warning. opened a new pari instead and it works fine so far.

[science_man_88]

Originally Posted by science_man_88

I was just going to eliminate a whole lot of possibilities other than a[f]==a[g], by changing it to vecsort(a[f],,4)==vecsort(a[g],,4) but at times I get a forbidden followed by a unknown type 48 warning. opened a new pari instead and it works fine so far.

I'm guessing I'm the one holding this up now if only I could get my code to work as intended I am trying to use an if to eliminate a lot of of them from needing to check much else at all beforehand:


1)if sorted version of vectors are equal
2)if first sorted vector's first value is less than any value after second sorted vector's 3rd element

are the main things I was trying to implement:

(e)->j=0;
k=1;
a=vector(3,b,vecsort(vector(6,b,d=0;until(d>0,d=random(e+1));d),,4));
for(f=1,3,
    for(g=
        if(f==1,2,
           if(f==2,3,
              if(f==3,1
                )
             )
          ),
       if(f==1,2,
          if(f==2,3,
             if(f==3,1
               )
            )
         ),
       if(vecsort(a[f],,4)==vecsort(a[g],,4) 
       || vecsort(a[f],,4)[1]<vecsort(a[g],,4)[6]
       || vecsort(a[f],,4)[1]<vecsort(a[g],,4)[5]
       || vecsort(a[f],,4)[1]<vecsort(a[g],,4)[4]
       || vecsort(a[f],,4)[1]<vecsort(a[g],,4[3]
       ,next(2)
         )
       );
       for(h=1,6,
            for(i=k,6,
                 if(a[f][h]<a[g][i],
                   k=k+1,
                   j=j+k*(e-h)
                   )
                )
           );
           if((j/(e^2))>.5,
              ,
             return(0)
              );
              j=0;
              k=1
             );
            return(1)

I think I may have found the error(s) in the process of putting it like this I just find it hard to make it that way in PARI.

[science_man_88]

Originally Posted by science_man_88

I'm guessing I'm the one holding this up now if only I could get my code to work as intended I am trying to use an if to eliminate a lot of of them from needing to check much else at all beforehand:


1)if sorted version of vectors are equal
2)if first sorted vector's first value is less than any value after second sorted vector's 3rd element

are the main things I was trying to implement:

(e)->j=0;
k=1;
a=vector(3,b,vecsort(vector(6,b,d=0;until(d>0,d=random(e+1));d),,4));
for(f=1,3,
    for(g=
        if(f==1,2,
           if(f==2,3,
              if(f==3,1
                )
             )
          ),
       if(f==1,2,
          if(f==2,3,
             if(f==3,1
               )
            )
         ),
       if(vecsort(a[f],,4)==vecsort(a[g],,4) 
       || vecsort(a[f],,4)[1]<vecsort(a[g],,4)[6]
       || vecsort(a[f],,4)[1]<vecsort(a[g],,4)[5]
       || vecsort(a[f],,4)[1]<vecsort(a[g],,4)[4]
       || vecsort(a[f],,4)[1]<vecsort(a[g],,4[3]
       ,next(2)
         )
       );
       for(h=1,6,
            for(i=k,6,
                 if(a[f][h]<a[g][i],
                   k=k+1,
                   j=j+k*(e-h)
                   )
                )
           );
           if((j/(e^2))>.5,
              ,
             return(0)
              );
              j=0;
              k=1
             );
            return(1)

I think I may have found the error(s) in the process of putting it like this I just find it hard to make it that way in PARI.

yet another simple thing only check for the third entry if the third isn't neither will the others.

[science_man_88]

Originally Posted by science_man_88

yet another simple thing only check for the third entry if the third isn't neither will the others.

sorry worded wrong basically unless you prove the third element is greater you have no guarantee of half.

[science_man_88]

Originally Posted by lavalamp

Based on actual runtime, my code for N=30 would run in a comparatively brief tens of millions of years.

what are you down to now ? if I did everything properly ( addmitedly I haven't found a way to do: "The sets of dice {A,B,C}, {B,C,A} and {C,A,B} are the same set." or a way to make sure they are all unique but even testing what I believe could be N^18 possibilities ( admittedly likely a lot less) I think I'm down to just over 2300 years. oh never mind that was my N=7 result.

[lavalamp]

Here is a fairly ginormous hint:

Perhaps you should look at how you could generate all combinations of two digits, remember that for a combination, the order they are in doesn't matter. eg. 19 OR 91, but not both, they are counted as the same combination, "a 1 and a 9".

If you count all the valid combinations, how many are there? [url=http://en.wikipedia.org/wiki/Triangular_number]Hint[/url].

How about combinations of 3 digits, how many combinations are there now? [url=http://en.wikipedia.org/wiki/Tetrahedral_numbers]Hint[/url].

Try this with various ranges of numbers, 1 to 2, 1 to 3 etc.

Now generalise it to 6 "digits" (or "sides of a die" in our case), and use 1 to 30 as your single digit range (if you can allow yourself to think of 30 as a single digit, just pretend you're working in base 31 or higher). Now you can generate all combinations of a die without repeats and in numerical order.

If you don't get the trick right away, that's fine, but think about it for a couple of days. If you can't initially write down code to generate 2 or 3 digit combos, just work them out on pen and paper until you see a pattern, if you restrict yourself to a digit range of 1 to 4 or similar, there aren't that many.

If you get stuck at some point and have questions, then as a general rule don't immediately post them. Wait a while and you might discover the answers yourself. Similarly if you work something out, don't post it immediately, work out as much as you can then post everything together at the end, it's much easier to read that way.

[science_man_88]

Originally Posted by lavalamp

Here is a fairly ginormous hint:

Perhaps you should look at how you could generate all combinations of two digits, remember that for a combination, the order they are in doesn't matter. eg. 19 OR 91, but not both, they are counted as the same combination, "a 1 and a 9".

If you count all the valid combinations, how many are there? [url=http://en.wikipedia.org/wiki/Triangular_number]Hint[/url].

How about combinations of 3 digits, how many combinations are there now? [url=http://en.wikipedia.org/wiki/Tetrahedral_numbers]Hint[/url].

Try this with various ranges of numbers, 1 to 2, 1 to 3 etc.

Now generalise it to 6 "digits" (or "sides of a die" in our case), and use 1 to 30 as your single digit range (if you can allow yourself to think of 30 as a single digit, just pretend you're working in base 31 or higher). Now you can generate all combinations of a die without repeats and in numerical order.

If you don't get the trick right away, that's fine, but think about it for a couple of days. If you can't initially write down code to generate 2 or 3 digit combos, just work them out on pen and paper until you see a pattern, if you restrict yourself to a digit range of 1 to 4 or similar, there aren't that many.

If you get stuck at some point and have questions, then as a general rule don't immediately post them. Wait a while and you might discover the answers yourself. Similarly if you work something out, don't post it immediately, work out as much as you can then post everything together at the end, it's much easier to read that way.

if you're working with n single digit possibilities it's n^ length for possible combinations , I already implemented vecsort (vector,,4) which sorts them if they have the same amount of things but in a different order I've already put it to return 0 now. so that destroys that in fact I was able to do a single N=9999^9999 last night in about 16 ms . 7^3 in less than 2 seconds as my timing was almost linear going for 7^4 took a little over 7 times the time but 7^18 = 7^18-3 times as many so it will take 7^15 times as long. maybe I should stop 377 is up I believe.

Euler376(e)=j=0;k=0;a=vector(3,b,vecsort(vector(6,b,d=0;until(d>0,d=random(e+1));d),,4));for(f=1,3,for(g=if(f==1,2,if(f==2,3,if(f==3,1))),if(f==1,2,if(f==2,3,if(f==3,1))),if(vecsort(a[f],,4)==vecsort(a[g],,4),return(0),if(vecsort(a[f],,4)[1]<vecsort(a[g],,4)[3],j=18));for(h=1,6,for(i=if(j==18,4,1),6,if(a[f][h]<a[g][i],k=k+1;if((k+j)>18,return(1)),j=j+k*(e-h))));if(j<=18,,return(0)));j=0;k=0);return(1)

[lavalamp]

Originally Posted by science_man_88

if you're working with n single digit possibilities it's n^ length for possible combinations

No, it is not. There are n^length PERMUTATIONS, which is not what is required here.

[science_man_88]

Originally Posted by lavalamp

No, it is not. There are n^length PERMUTATIONS, which is not what is required here.

yeah I'm looking at 377 for now I'll get back 376 some time. I've already got a script for what they seem to mean already except I've never heard digital sum used that way ( or at least not for just those types of numbers).

[voidme]

377 is hilarious

there is an OEIS sequence but it's incorrect

[science_man_88]

Originally Posted by science_man_88

yeah I'm looking at 377 for now I'll get back 376 some time. I've already got a script for what they seem to mean already except I've never heard digital sum used that way ( or at least not for just those types of numbers).

well because I have 2 versions of PARI I have 2 different things ( though the second is in partial due to CRG, because it's an alteration of a code he gave to me for a different purpose) first one:

(n)->d=0;forstep(x=n,(10^n-1)/9,9,if(vecsort(eval(Vec(Str(x))),,8)[1]==0,next(1),if(sum(X=1,#vecsort(eval(Vec(Str(x))),,4),vecsort(eval(Vec(Str(x))),,4)[X])==n,d=d+x)));d

the second one:

(n)->b=0;a=Vec(select(v->vecmin(v)>0,partitions(n)));for(x=1,#a-1,b=b+((10^#a[x]-1)/9)*n);for(v=1,#a[#a],b=b+a[#a][v]*10^(#a[#a]-v));b

neither is completely work for the problem as they run out of memory.