[superprismatic]

Consider the first 1001 digits of pi (ignore the

decimal point):

3.

14159265358979323846264338327950288419716939937510

58209749445923078164062862089986280348253421170679

82148086513282306647093844609550582231725359408128

48111745028410270193852110555964462294895493038196

44288109756659334461284756482337867831652712019091

45648566923460348610454326648213393607260249141273

72458700660631558817488152092096282925409171536436

78925903600113305305488204665213841469519415116094

33057270365759591953092186117381932611793105118548

07446237996274956735188575272489122793818301194912

98336733624406566430860213949463952247371907021798

60943702770539217176293176752384674818467669405132

00056812714526356082778577134275778960917363717872

14684409012249534301465495853710507922796892589235

42019956112129021960864034418159813629774771309960

51870721134999999837297804995105973173281609631859

50244594553469083026425223082533446850352619311881

71010003137838752886587533208381420617177669147303

59825349042875546873115956286388235378759375195778

18577805321712268066130019278766111959092164201989

Now, let P(i) be the i^th digit of pi,

where i is in [1,1001]. Your task is

to find a 10-long vector of non-zero

integers V such that the sum of the

absolute values of the dot products

of V with P at all possible positions

inside P produces a minimum value.

That is, let

Q(V)=sum{i=0,991}[abs(sum{j=1,10}[P(i+j)*V(j)])]

where {i=a,b} means 'i varies over

all integer values in the closed

interval [a,b].'

Find V and its Q(V) such that Q(V) is

as small as possible.

Edited December 28, 2009 by superprismatic

[Guest]

I would imagine that the vector would be <1,1,1,1,1,1,1,1,1,1>...but if not, then I think that you have to use a program...there isn't really a "clever" way...

[soop]

Wow.

I think this puzzle is for people smarter than me. I'll stick to Professor Layton.

[Guest]

I might just be misunderstanding something, but it seems to me that the text description is not the same as the description with mathematical notation. Shouldn't it be Q(V)=sum{i=1,1001}[abs(sum{j=1,10}[P(i)*V(j)])] if we are to use "all possible positions inside P"?

[superprismatic]

I might just be misunderstanding something, but it seems to me that the text description is not the same as the description with mathematical notation. Shouldn't it be Q(V)=sum{i=1,1001}[abs(sum{j=1,10}[P(i)*V(j)])] if we are to use "all possible positions inside P"?

What I meant by "all possible positions inside P" was:

abs(P(1)*V(1)+P(2)*V(2)+P(3)*V(3)+P(4)*V(4)+P(5)*V(5)+P(6)*V(6)+P(7)*V(7)+P(8)*V(8)+P(9)*V(9)+P(10)*V(10))+

abs(P(2)*V(1)+P(3)*V(2)+P(4)*V(3)+P(5)*V(4)+P(6)*V(6)+P(7)*V(6)+P(8)*V(7)+P(9)*V(8)+P(10)*V(9)+P(11)*V(10))+

abs(P(3)*V(1)+P(4)*V(2)+P(5)*V(3)+P(6)*V(4)+P(7)*V(7)+P(8)*V(6)+P(9)*V(7)+P(10)*V(8)+P(11)*V(9)+P(12)*V(10))+

abs(P(4)*V(1)+P(5)*V(2)+P(6)*V(3)+P(7)*V(4)+P(8)*V(8)+P(9)*V(6)+P(10)*V(7)+P(11)*V(8)+P(12)*V(9)+P(13)*V(10))+

                                   .

                                   .

                                   .

abs(P(992)*V(1)+P(993)*V(2)+P(994)*V(3)+P(995)*V(4)+P(996)*V(8)+P(997)*V(6)+P(998)*V(7)+P(999)*V(8)+P(1000)*V(9)+P(1001)*V(10))

[/code]

I was thinking of "sliding" the 10-long V vector thru all consecutive 10-long segments of P.

By the way, V can have positive and negative elements but may not have a zero element.

Although I have a favorite vector V together with a relatively small Q(V), it may not

be the smallest possible.  I'm curious to see if anyone can find something better.

[Guest]

If I've done this correctly, I seem to be getting the following results:

0

15 -15 14 20 6 6 -15 -7 -18 -6

Let me know if this shouldn't be happening, and I'll see if I can find out where I've made a mistake in my programming.

[Guest]

Or:

1 1 -1 1 -1 -1 1 1 -1 -1

Also with a Q(V) of 0, assuming that my programming is correct.

[superprismatic]

If I've done this correctly, I seem to be getting the following results:

0

15 -15 14 20 6 6 -15 -7 -18 -6

Let me know if this shouldn't be happening, and I'll see if I can find out where I've made a mistake in my programming.

15 -15 14 20 6 6 -15 -7 -18 -6 Q(V)=96045

[superprismatic]

Or:

1 1 -1 1 -1 -1 1 1 -1 -1

Also with a Q(V) of 0, assuming that my programming is correct.

1 1 -1 1 -1 -1 1 1 -1 -1 Q(V)=7322, which is very good but still a bit bigger than my best.

Getting zero is probably an indication of a bug. After all, Pi is pretty random!

Edited December 30, 2009 by superprismatic

[Guest]

Ah, bug found.

V: 1 1 1 1 1 -1 -1 -1 -1 -1 (veeery pretty, might I add)

Q(V): 6898

[superprismatic]

Ah, bug found.

V: 1 1 1 1 1 -1 -1 -1 -1 -1 (veeery pretty, might I add)

Q(V): 6898

I'm not using spoilers because this problem is not a puzzle with a known answer.

I checked your answer and for your V=(1,1,1,1,-1,-1,-1,-1), I also compute Q(V) to be 6898.

Notice that, because of the absolute value in the function Q, Q(V)=Q(-V). So, Q(V)=6898

for V=(-1,-1,-1,-1,1,1,1,1) as well. Will you give a short description of what your program

does? Is there a lot of guessing? Is a genetic algorithm involved? Did you use one of the

methods (like the Simplex Algorithm) to optimize Q(V)? Also, do you have any clue as to

why the V you got is so pretty? Perhaps it's a property of Pi itself. I hope we can get

even better answers than the pretty one you found.

[Guest]

I actually had the same thought, and tested it with some random lists of digits of same length; none of those end up with the same result for minimum Q(V) as for pi, so I'm thinking that it's something in particular with pi. Which is fascinating in and of itself, really.

I don't know enough about algorithms to be able to name the method I used, but I can describe it. I made four functions:

A. Creates a vector of length 10, with random integers ranging from -x to x, where x is user-chosen.

B. Checks whether the vector contains a zero or not. If it does, the vector is discarded. If not, it is kept.

C. Finds the dot product as per the instructions in the puzzle.

D. Runs functions A, B and C n times, where n is user-chosen, and returns the lowest Q(V) found with its corresponding V.

I then ran function D with a million iterations, using x=1. I also tested it with x=100, but this only gave larger values for Q(V), for what I consider intuitive reasons.

If one indeed can assume that Q(V) will always be lowest with x=1, then I have a more systematic idea for how to solve this - i.e. by running function D for the 2^10=1024 permutations of -1's and 1's specifically, rather than picking random V's.

Liked the puzzle, thanks for that