Problem 097

[Phibonacci]

Is the number like this:
28433×(2^7830457+1)
or:
(28433×2^7830457)+1

[Tommy137]

Is the number like this:
28433×(2^7830457+1)
or:
(28433×2^7830457)+1

(28433×2^7830457)+1 is correct.

[JMW1994]

Is 28433×2^7830457+1 calculated like this (28433×2^7830457)+1 or 28433×(2^7830457+1)? It appears that either way, I can't get to the correct answer. The fastest way is to only focus on the last 10-20 digits rather than the 2,000,000+ number as a whole.

[TripleM]

If it were the latter, it wouldn't exactly be a prime, would it?

[JMW1994]

<snip>
Is it possible to even calculate +2,000,000 digits with an array or linked list?

[elendiastarman]

JMW1994, one would think that having been on this forum for several months and posting 28 other times, you should know not to post any results or code, whole or fragmented. In addition, you should also know that this is a public forum. Hence, can you remove your results?

[JMW1994]

Okay, they weren't right though. However, can one actually calculate a +2,000,000 digit through an array or linked list?

[mynameisalreadytaken]

It's surely possible - with an arbitrary precision library you could calculate all digits of the number. But this is absolutely not necessary.

[JMW1994]

It's surely possible - with an arbitrary precision library you could calculate all digits of the number. But this is absolutely not necessary.

I already knew that as I already programmed an arbitrary precision library(I call it "system" instead) but maybe it was how the order of 28433×2^7830457+1 went.

EDIT: Solved it. Had to do with something in the library that I wrote up.

[marvin]

Hi,
I have a BigInt class in C#, but it calculates powers up to ~5000.
So I decided (for this question) to treat every number >10^10 as its last 10 digits, and multiply that (max. 10 digit) number by 2 to get the next power.

is this approach true? I mean I think it would be true , but in the end, I got the last 10 digits and multiply that number by 28433 and added 1. But the answer is not correct.
So what's wrong with this solution?

[thundre]

So what's wrong with this solution?

Does the end result have more than 10 digits? If so, you should drop some, because the problem only asks for 10.

[marvin]

So what's wrong with this solution?

Does the end result have more than 10 digits? If so, you should drop some, because the problem only asks for 10.

Yes, I entered the last 10 digits of the result.
Apparently something wrong with my program.

[marvin]

Omg,
I gave up that one and tried another solution, which failed again:

I tried to find a pattern, and discovered that the last 2 digits of powers of two repeat themselves in every 20^th power.
So I got (28433 % 20) , and the corresponding two digit number, multiplied that with 2²⁰, multiplied by 28433, added 1, and... wrong!

somebody please give a clue where am I doing wrong?

edit: oops, I understood what's wrong with my second solution. gotta find a bigger-digit pattern.

edit 2 : found the bigger pattern, still wrong.. this question is gonna drive me crazy..

[TheEvil]

If you were asked the last two digit of this number, your answer would almost be good. But you have to calculate
(28433%100) × 2^7830457%20 + 1
and of course at the end, the last two digit of that number. Anyway the problem is solvable without bigintegers (as all the others I have done yet).

[rayfil]

marvin

Just make sure you multiply by 2 the correct number of times. Try your algo with a smaller power (such as 4321) and see how it checks with the result you would get with your BigInt class.

[hkapur97]

This problem can be done by hand if you're very good with [modular arithmetic](en.wikipedia.org/wiki/Modular_arithmetic)