Sum of Digits

[Jayder]

If that's only running on one core, mine is abysmally slow in comparison to yours. If it's different from what Kevin posted, would you mind sharing the code? I might learn something.

[davar55]

You might want to check out OEIS sequence A135738.

[Jayder]

m_f_h's code is better written than mine, but it's slower in its unoptimised state.

I see that the OEIS entry still asks why a(2n+1)=a(2n). I was able to figure out why, but as this is the Puzzles subforum I won't share the answer, particularly because it's not hard to figure out. It also answers why, after base 2, it is always an even number.

[legendarymudkip]

The code I used for the benchmarking is at http://pastebin.com/pjUAD0Ys . It can definitely be improved upon, but I don't know enough about optimization of C++ for this - I don't know what language you were using but it's just about possible that's some of why it was faster. Another possibility is hardware, as although it was run on 1 core, it was 1 core of an i5-4670k.

[davar55]

Originally Posted by Jayder

...
I see that the OEIS entry still asks why a(2n+1)=a(2n). I was able to figure out why, but as this is the Puzzles subforum I won't share the answer, particularly because it's not hard to figure out. It also answers why, after base 2, it is always an even number.

Why not post it here? The oeis entry points here anyway.

[Jayder]

Originally Posted by davar55

Why not post it here? The oeis entry points here anyway.

I'm sorry if I'm being annoying. I had fun figuring it out, and I don't want to deprive you (or anyone else) of that joy. It's an easier problem than you might think. Let me transform the problem for you, which will give you the same hint that I had:

Let's take this list and change it to tell us the highest base in the unbroken chain.

n		highest base

6		3
10		5
54		9
130		13
390		15
2000		17
3238		19
4080		21
7326		23
16584		25
17310		33
231000		37
466352		41

Do you see anything in common with the numbers in each column? It's very simple. If nobody beats me to it I'll post the answer when I get bored.

[axn]

digitsum(n,b) == n (mod (b-1)) [which is the basis for "divisibility by 9" shortcut]

For odd b, 2 | (b-1). Rest follows.

[Jayder]

For those that didn't understand, axn just explained that, given an even n and an odd b, you will always have an even digit sum. This is roughly how I figured it out:

Let's give '1234' in ternary: 1200201. How can you convert it back into decimal? Forgive my inexact wording here: You find the value of each digit and add them together. For example, since it's ternary, the rightmost digit's value is 1*3^0. The full sum is 1*3^6 + 2*3^5 + 0*3^4 + 0*3^3 + 2*3^2 + 0*3^1 + 1*3^0 = 1234₁₀.

We know that an odd number multiplied by another odd number is going to give an odd result, and that an even number added to an odd number gives an odd number. I'm going to skip a bit here, but in order for our sum above to result in an even number (1234), we needed to have an even number of odd digits in our converted base. An even number of odd digits, as might be obvious, is required to have an even sum of digits. So: Even though our example used ternary, an even number in any odd base will have an even amount of odd digits. Therefore, there is no point in testing odd bases, as they will always "pass".

Now I wait for somebody to tell me how crap my explanation was.

[LaurV]

Originally Posted by Jayder

Let's give '1234'

Hey, how do you know my password?

[axn]

As continuation from the last OEIS entry, here are the successive records.

base = 46 @ n = 3020830
base = 50 @ n = 13655684
base = 60 @ n = 247783834
base = 68 @ n = 15414298020
base = 76 @ n = 43427482624
base = 78 @ n = 731006573462
base = 80 @ n = 1251455242678
base = 82 @ n = 12729637799668
base = 88 @ n = 19807076334958
base = 94 @ n = 180942524431476
base = 98 @ n = 188893618365750
base = 102 @ n = 632712065014988

[Jayder]

Whoa, how did you do that?