Problem 16 – One Liner

by

I spent a little while trying to come up with some inductive (or other clever) way to compute the sum of the digits of 2^n, without just implementing multiplication by 2. Mostly I did this because I figure 2^{1000} is pretty big, and maybe having a script compute that number would cause some sort of issue. Not coming up with anything particularly clever, I thought I’d try just a naive approach: compute 2^{n} directly and then sum the digits. Here’s the one-liner (not counting “import sys”) I came up with:

print sum(map(int,str(int(sys.argv[1]))))

Delightful. Even better – my initial concern that something would go wrong (take a while, use up too much memory) was apparently unfounded. This script ran without any noticeable difficulty in just a fraction of a second. It also did fine with a power of 10,000 and 100,000 (taking a little more than a second here). For 1,000,000, it took close to 2 minutes. This still makes me wonder if there’s a clever way to solve this problem quickly for big powers.

I thought I’d see what the function f(n)= the sum of the digits of 2^n looked like. Here’s a sampler:

Kinda fun, I think. Then I thought: how about just g(n)= sum of the digits of n. I encourage you to spend up to 10 seconds thinking what this graph should look like.

Tags: ,

One Response to “Problem 16 – One Liner”

  1. Problem 20 – One More Line « Leonhard Euler’s Flying Circus Says:

    […] problem is pretty similar to Problem 16, which I also wrote about. There are probably improvements to be made. Like, you might as well start the xrange at 2, instead […]

Leave a Reply

Fill in your details below or click an icon to log in:

WordPress.com Logo

You are commenting using your WordPress.com account. Log Out /  Change )

Google photo

You are commenting using your Google account. Log Out /  Change )

Twitter picture

You are commenting using your Twitter account. Log Out /  Change )

Facebook photo

You are commenting using your Facebook account. Log Out /  Change )

Connecting to %s


%d bloggers like this: