Project Euler/16

← Back to User:ProjectEuler

Project Euler Problem 16 is a problem related to the powers of 2. The task is to find out the "digit sum" (sum of all digits in decimal expansion) of 2¹⁰⁰⁰.

This article is not detailed enough and needs to be expanded. Please help us by adding some more information.

Implementations

Aheui

This pattern works on both AheuiChem^{[citation needed]} and Try It Online. It uses the "decimal multiplication calculator" algorithm which theoretically works for an arbitrarily large number multiplied by a non-zero digit. It also contains some weird parts, for example, a path branches into two and then the two branches joins up immediately, or paths that branches immediately back to itself.

밣발발발따따따밣밣발따따뿌터너벌
ㅇㅇㅇㅇㅇㅇㅇ쑥너벌벌머차바싹볼
ㅇㅇㅇㅇㅇㅇㅇ뿌터너벌벌서
ㅇㅇㅇ아더뭉셕차숙머어ㅇ오쎤너더벊벌아셕어
ㅇㅇㅇㅇㅇ희무선빠박따빠발발다라싼샨오더오
ㅇㅇㅇㅇ먀썩뻐ㅇㅇㅇㅇㅇ요

APL (Dyalog)

+/⍎¨⍕2*1000

Chinese

加全数迭串二幂一〇〇〇

C

#include <stdio.h>
int a[320]={1},k,l,r;

void flow(int d[]){
    int i;
    for(i=0;i<319;++i){
        d[i+1]+=d[i]/10;
        d[i]%=10;
    }
}
int main(){
	for(k=1;k<=1000;++k){
		for(l=0;l<320;++l){
            	 a[l]*=2;
        	}
        	flow(a);
	}
	for(l=0;l<320;++l){
		r+=a[l];
	}
	printf("%d",r);
    return 0;
}

C♯ (.NET)

using System;
using System.Numerics;

class Program {
    static void Main() {
        BigInteger n = BigInteger.Pow(2, 1000);
        int sum = 0;
        foreach (char c in n.ToString()) sum += c - '0';
        Console.WriteLine(sum);   // 1366
    }
}

Gofe

/g8/&da&q2Pd[&sQqAt&t#sGqF]#t.

I fuck, you fuck

There's a fucker named a
Fuck a 2000 times
There's a fucker named b
Fuck b 2 times
b fucks a over and over
b unfucks b
There's a fucker named c
while a is fucked
c unfucks c
Fuck c 10 times
a unfucks c over and over
c fucks b
c unfucks c
Fuck c 10 times
a unfucks c again
a unfucks a
c fucks a
end fuck
b fucks you

Java

import java.math.BigInteger;

public class Euler16 {
    public static void main(String[] args) {
        BigInteger n = BigInteger.valueOf(2).pow(1000);
        String s = n.toString();
        int sum = 0;
        for (char c : s.toCharArray()) {
            sum += c - '0';
        }
        System.out.println(sum);   // 1366
    }
}

Julia

n = BigInt(2)^1000
sum_digits = sum(parse(Int, c) for c in string(n))
println(sum_digits)   # 1366

Lua

digits = {1}  -- least‑significant digit first
for _ = 1, 1000 do
    carry = 0
    for i = 1, #digits do
        prod = digits[i] * 2 + carry
        digits[i] = prod % 10
        carry = math.floor(prod / 10)
    end
    while carry > 0 do
        table.insert(digits, carry % 10)
        carry = math.floor(carry / 10)
    end
end
sum = 0
for i = 1, #digits do sum = sum + digits[i] end
print(sum)   -- 1366

Pascal

program Euler16;
var
  digits: array[0..400] of integer;
  len, exp, j, carry, prod, sum: integer;
begin
  digits[0] := 1;
  len := 1;
  for exp := 1 to 1000 do
  begin
    carry := 0;
    for j := 0 to len - 1 do
    begin
      prod := digits[j] * 2 + carry;
      digits[j] := prod mod 10;
      carry := prod div 10;
    end;
    while carry > 0 do
    begin
      digits[len] := carry mod 10;
      carry := carry div 10;
      len := len + 1;
    end;
  end;
  sum := 0;
  for j := 0 to len - 1 do sum := sum + digits[j];
  writeln(sum);   // 1366
end.

Python

#Euler Problem 16
#by Europe2048

def sumdigits(n):
	sum = 0
	for i in str(n):
		sum = sum + int(i)
	return sum
print(sumdigits(2**1000))

Alternate implementation (shorter), by None1:

print(sum(map(int,str(2**1000))))

Another implementation by User:PrySigneToFry:

print(sum(int(d) for d in str(2**1000)))

Fourth implementation by User:PrySigneToFry:

m = 2 ** 1000
k = 0
while m < 1:
    k += m % 10
    m //= 10
print(k)

Text

1366

External resources

• A001370, a related sequence on OEIS. The 1001st term is the solution.
• Problem 16 on Project Euler Official Website (not available)
• Problem 16 on Project Euler Mirror