# Weird Sums

1. Jun 12, 2008

### Dragonfall

I'd like to see whether weird reciprocal sums of integers in the form $$\sum_{x\in S}\frac{1}{x}$$, where S is some unconventional set of integers, converges or diverge. Does anyone know any?

For example, $$\sum_{x\in S}\frac{1}{x}$$ where S is the set of integers that, when expanded in binary, represents a valid Java program compiled on the x86 architecture. Is it convergent? Divergent?

2. Jun 12, 2008

### Santa1

edit: Well in that case if S is symmetric about 0 you also see something interesting happening. But with 1/x as a summand the sum is usually divergent.

Last edited: Jun 12, 2008
3. Jun 12, 2008

### Dragonfall

I suppose we'll have to remove 0 from the sets.

4. Jun 12, 2008

### Vid

The set of binary numbers would have to be finite so convergence or divergence isn't really a question. If the set is infinite, it depends on the set. The set of all squares is convergent, but the set of all even numbers is divergent.

5. Jun 12, 2008

### uman

"A valid Java program compiled on the x86 architecture" is meaningless.

"A valid program compiled for the Java VM" might not be.

6. Jun 12, 2008

### Dragonfall

Well then let's go with "a valid program compiled for the java VM". Does it converge?

The set of integers is not finite, expressed in binary or otherwise.

7. Jun 12, 2008

### Vid

I meant a set of binary numbers representing a program would have to be finite.

8. Jun 12, 2008

### uman

But the set of all integers representing a program isn't...

9. Jun 13, 2008

### Dragonfall

Like Uman said, the set of all binary numbers which represent a program is not finite.

10. Jun 13, 2008

### indrifan

Here's a 'top of the head' answer - I haven't actually worked it out. But I suspect the java example converges (edit - diverges). Here's my thinking: the simplest valid java program would just be some declaration of a constant (say a string), along with a bit of overhead. So there would be a sequence of valid programs where the constant value increases by 1 in the coding representation. The question is, what happens when a new byte needs to be added? Can we always get away with just adding one more byte to the binary (I don't know enough about java byte-coding to wnaswer that). Is it ever the case where the consecutive gaps between valid programs are large enough that the sum of their inverses converge? I strongly suspect the answer is no, but I don't have time right now to work out the details. If someone else doesn't beat me to it, maybe I'll work through it this weekend.

edit - oops. I meant to say diverges.

Last edited: Jun 13, 2008
11. Jun 13, 2008

### Dragonfall

It depends on how Java "enumerates" programs. Two different enumerations of Turing machines, for example, might give a convergent and a divergent sum. For example, in one enumeration all valid programs are enumerated at powers of 2, and in the other it's the opposite.

EDIT: In fact, I think the Java example diverges. Any set containing an infinite arithmetic progression leads to a divergent sum, and maybe that Java binaries set contains such a sequence.

Last edited: Jun 13, 2008
12. Jun 13, 2008

### indrifan

Yes. But I'd be very surprised if the java byte-code compiler used any kind of sparse coding, much less exponential. I think it's much more likely that it's going to be linear, so S will look a lot more like {x: x=m + 1} for some minimum m chars of overhead.

If we were talking about Godel-numbering, or some such scheme, then the "weird set" will almost certainly converge. But that's because Godel numbers are constructed so as to have lots of desirable properties when considered "all at once", as a number. There's no need for the Java VM to consider programs in that way - so it will fill the "valid program space" much more efficiently, i.e. much more densely.

13. Jun 13, 2008

### indrifan

@Dragonfall, I posted while you were editing. Sounds like we're in agreement.

I'm not sure my last post was actually coherent - but I hope my point gets across.
What I'm trying to say is that, in order to find a set you're talking about that converges, you'll have to find some set S that "grows fast". One potentially interesting example that springs to my mind is Ramsey numbers.

14. Jun 13, 2008

### Vid

Oh, I thought we were taking the binary from a JAVA program and creating a set of integers from that. Not the set of integers that could represent any JAVA program. My bad.

15. Jun 13, 2008

### Dragonfall

Ok what about this, the set of perfect numbers? You don't have to solve the question of whether there are infinitely many, since you can show (somehow) that the sum is finite (or even rational), a la Brun's constant.