find the last ten digits of 1^1 + 2^2 + ... + 1000^1000

how to Create a function to find the last ten digits of 1^1 + 2^2 + ... + 1000^1000 using M-script

[José-Luis]

What have you tried so far?

[Roger Stafford]

If you use the proper method you can compute it numerically. The sixth digit from the right end of the answer is an '8'. That leaves you nine others to discover.

[Vivek]

%last ten digits of 1^1 + 2^2 + ... + 1000^1000

y=0; b=0;

for x=1:1000

    y=y+(x^x);
    y=mod(y,10000000000); %to get the last ten digits
end
disp(y)

[Walter Roberson]

No, that will not work. x^x can exceed 2^53 and so x^x would have lost digits before being added to y. This starts happening from 14 onwards. And after 142, x^x would be calculated as infinity because it exceeds 1E308

[Jan]

See [EDITED] in my answer below: Avoid calculating x^x explicitly, when you need the last 10 digits only.

Answer 1

[Walter Roberson]

http://www.mathworks.com/matlabcentral/fileexchange/7908-big-modulo-function

http://www.mathworks.com/matlabcentral/fileexchange/38516-powermod

Answer 2

[Jan]

You do not have to calculate i^i explicitly to find the trailing n digits of this number. It is enough to get the trailing n digits of each partial product, which can be achieved by the mod command. The same can be applied for the sum also. Finally 8 lines of very straight Matlab code are enough, and no special toolbox functions are required.

Computing time is 0.025 seconds on my Core2Duo, Matlab2009a/64. The last digit appears 3 times.

[EDITED] As said already, you can get the last 10 digits of x^x without calculating this potentially large value explicitly:

P = 1;
for ix = 1:x
  P = mod(P * x, 1e10);
end

Now P contains the last 10 digits of x^x. Ok? The sum can be created equivalently.

Limitation: This fails, when x*1e10 exceeds 2^53.

[Walter Roberson]

FEX 7908 that I linked to does a binary decomposition to minimize the number of multiplications.

[Jan]

@Walter: I personally like the linked function. I assume that vivek cannot submit a solution of this homework question (at least I'm convinced that this is a homework) based on this function.

8 lines of straight basic Matlab code and 0.025 seconds processing time are a good argument to "keep it simple stupid".

[Vivek]

yes walter. but I need to do that upto 1000^1000

[Vivek]

@Jan: You are correct. I am working in a company and there they training me in matlab

[Walter Roberson]

binary decomposition of the exponent is a technique that will work fine up to

(2^52)^(2^52)

[Jan]

@vivek: It looks like you got 4 working solutions in this thread. Is your problem solved now?

Answer 3

[Sean de Wolski]

This is a good way to jog the brain for the first time in 2013!

last10 = trailingdigit(sum(vpi(1:1000).^vpi(1:1000)),10)

FEX:vpi

[Vivek]

It is giving a error ??? Undefined function or method 'vpi' for input arguments of type 'double'.

[Walter Roberson]

Did you download and install the vpi functions from the File Exchange (FEX) submission that Sean linked to?

[Vivek]

I am sorry walter. Its not possible. because I am working on matlab in my office

[Walter Roberson]

Then you cannot use Sean's approach. You should, however, be able to look at the source for the two FEX contributions I pointed out, and copy and paste the source into a local file.