Project Euler Forum

Since problem 188 is postponed for a week, perhaps this problem can help cure the empty, hungry feeling . It was a problem proposal that didn't make it because Maple and Mathematica can find the answer with a single trivial statement. Not using a CAS the problem is quite challenging though. If you solved it correctly, you may to follow this link . Good luck:

Here is another one you might try.
1,1,2,3,5,8,13,21... are the wellknown Fibonacci numbers with recurrence relation F(n)=F(n-1)+F(n-2).

If we take every second Fibonaccinumber we get the sequence:
1,3,8,21,55,144...
Let's call these numbers G₂(n).
These seem to follow the recurrence relation G₂(n)=3G₂(n-1)-G₂(n-2).

If we take every third Fibonaccinumber we get the sequence:
2,8,34,144,610
Let's call these numbers G₃(n).
Find a₃,b₃ so that G₃(n)=a₃G₃(n-1)+b₃*G₃(n-2).

Of course we could also take every p-th Fibonnaci number.
Generalise b_p and find a recurrence relation for the numbers a_p

Perhaps this is known stuff for you.
Otherwise have fun. If you think you solved it go to this link

hk wrote:Here is another one you might try.
1,1,2,3,5,8,13,21... are the wellknown Fibonacci numbers with recurrence relation F(n)=F(n-1)+F(n-2).

If we take every second Fibonaccinumber we get the sequence:
1,3,8,21,55,144...
Let's call these numbers G₂(n).
These seem to follow the recurrence relation G₂(n)=3G₂(n-1)-G₂(n-2).

If we take every third Fibonaccinumber we get the sequence:
2,8,34,144,610
Let's call these numbers G₃(n).
Find a₃,b₃ so that G₃(n)=a₃G₃(n-1)+b₃*G₃(n-2).

Of course we could also take every p-th Fibonnaci number.
Generalise b_p and find a recurrence relation for the numbers a_p

Perhaps this is known stuff for you.
Otherwise have fun. If you think you solved it go to this link

That was really fun. I searched the factors of the first 4 sequences by hand and found a nice pattern, which seems to hold for later sequences.

Was this another problem proposal?

No,

yesterday I went through some old problems and was redoing Problem 2, when I came up with this.
Thought it nice but more fun the way I presented it here than as PE problem.
Perhaps it's a nice idea to look whether the a_psequence you found is in OEIS.

 

Henks problem involves some heavy number theory I don't understand. Interestingly the problem was solved in 1631!

[spoiler]Some research gave mathworld.wolfram.com FaulhabersFormula.html


And then in Maple:

KroneckerDelta := (i, j) -> if (i = j) then 1 else 0 end if;
Faulhaber := (p, n) -> (1/(p + 1)) * sum((-1)^KroneckerDelta(i, p) * binomial(p+1, i) * bernoulli(p+1-i) * n^i ,i=1..p+1);

evalf(log10(Faulhaber(337, 10^14+1)));
4729.471081

evalf(Faulhaber(337, 10^14+1) / (10^4719), 11);
29585798817. 10^11

So the answer is 2 958 579 881[/spoiler]

There's a much simpler approach
[spoiler]use a Riemann sum and you get 1/338*(10^14)^338
or simply calculate the first ten nonzero digits of 1/338[/spoiler]

[spoiler]Very interesting solution, and it works for 10 digits.

The first few numbers from the Faulhaber function solution is
2958579881 66180473372781345922090729783037475345114968526627218934911242617...

And 1/338 gives

0.002958579881 656804733727810650887573964497041420118343195266272...[/spoiler]

Care to calculate the difference?
Say subtract the first 25 nonzero digits of both?