Base prime number system possible?

September 12, 2004 8:53 AM

I read The Curious Incident of the Bear in the Night-Time and one of the bits of cleverness is using primes to number the chapters. This got me thinking, is it possible to have a base prime number system? [math inside]

Googling brought me a bunch of sites that say that prime numbers are prime for any integer base, but nothing about using a sequence as a base.

The two problems I see with using the prime sequence is that it is hard to check very large numbers and that it accelerates slowly, leading to long strings of 0s in any number.

A more general question would be can numbers be expressed in base f(x)? I know for base n, f(x) = n^x but does it have to be?

posted by revgeorge to science & nature (24 comments total)

BTW, here's some small base 10 numbers and their base prime equivalents:
1 = 1, 2 = 10, 3 = 100, 4 = 101 (or 20), 5 = 1000, 6 = (110 or 10001 or 30), 7 = 10000
posted by revgeorge at 8:59 AM on September 12, 2004

not an answer to your question, but godel numbering (i think that's the right term) is something like this. part of the proof of godel's famous incompleteness theorem (which says something (i'm no expert) along the lines of: "any sufficiently strong formal system cannot be complete" - in other words that you can't prove everything in maths, roughly) requires the encoding of "sentences" in a "language" as numbers. the trick is to number each word in the language and then generate a number by multiplying together primes.

consider the language consisting of the words "tom" "likes" "hates" "anne". if we number those as 1, 2, 3 and 4, then "tom likes anne" is encoded as 2 x 3x3 x 7x7x7x7. the list of primes is 2,3,5,7... and they correspond to the word ordering. so 2 is the first word, and 2 occurs once (1), so the first word is "tom". the next word is represented by 3 which occurs twice (2) so is "likes" and the third word is represented by 7, which occurs 4 times so is "anne".

"anne hates tom" would be 2x2x2x2 x 3x3x3 x 5.

if you think about it, this is pretty neat. given a number you can find factors and work out what the sentence is - even though the whole thing is squashed into a single number.

just thought i'd throw that in. if anyone is interested in all this, they might like reading this.
posted by andrew cooke at 9:07 AM on September 12, 2004

answering your question, you have to be more precise. rather than the "base" it's better to talk about the position values. for base 10, the position values are 1,10,100,...10^n.... i think what you're saying is, can the position values be primes: 1,3,5,7...

i did write if so, then the answer is that you can use anything that doesn't increase "too fast", so that the position value at (n+1) is greater than the biggest number you can specify using the positions 1..n. i'm sure that's the case for primes, but can't remember the details. however, that missed a crucial detail:

what digits are you allowed to use? in a fixed base system, it's obvious. base 10 uses 0-9, base 2 uses 0-1 etc. but what are the digits in your case? should it vary from position to position? i don't think there's an obvious answer. until i think of one, i'll just post this (and note that the other thing you need to worry about, once that's decided, is numbers that can be written down in more than one way).
posted by andrew cooke at 9:24 AM on September 12, 2004

Is there a sequel to the book? "Bear"?
posted by yerfatma at 9:27 AM on September 12, 2004

ah, reading your later post, i think you're using just 0 and 1. in that case, you will be ok as long as primes don't increase faster then 2^n. again, i'm sure that's true (it's mcsomething's theorem/lemma/wild guess...)

but you get ambiguities. weights are 1,2,3,5,7,11,13,17... so 20 could be written as 10000100 or 1010000 or 110010 or...?
posted by andrew cooke at 9:29 AM on September 12, 2004

but that answers my prev question really. using just 0 and 1 is the most restrictive you can be. and even that's possible. so the answer is yes, but you don't have unique representations for numbers.

i'll shut up now.
posted by andrew cooke at 9:31 AM on September 12, 2004

Your third post shows why a number-place-type system (where the location of each digit defines its value, vs something like roman numerals, which are a clusterfuck) ought to have powers of a particular number for each place-value. Having primes as the place-values immediately brings two problems to mind.

First, if you have primes as digit-values, you will have some redundancy - some of the counting numbers can be represented different ways. Once you added or subtracted (I'm not sure multiplication or division methods, as we know them, would work), you'd have to normalize the digits-- each counting number would have a canonical form with the leftmost digits as large as possible, and other nonstandard forms.

Then there would be the problem of the physical digits. Would you know, offhand, whether the seventh digit (from the right) could validly be '5'?

There is an underlying pattern to the primes (mumble-mumble Riemann Hypothesis), but the pattern is so obscure that at the number values we deal with regularly the seeming irregularity of the primes makes it rather difficult to quickly look at a number and know how big it is.

Secondly, large numbers cannot be represented by anything but their digital expansion - (decimal) scientific notation would have no meaning in this proposed digit system. From a practical standpoint, working with rally big or really small numbers would become onerous, if for no other reason (I"ve got another below) and you couldn't work with 1) only the coefficients,then 2)only the exponent/magnitude to arrive at an answer.

The ancient Egyptians apparently had something like this for their description of numbers less than one - they used sums of fractions. It would be very easy, however, to accidentally make decimals that totaled up to greater than one - 0.111 in your number system would mean zero wholes, a half, a third, and a fifth - which , if you total them up, would give you 1.03333(in base ten).

I think a prime-digit number system would be wayyyy too unwieldy, especially vs place-value systems. A reasonalby bright second grader can be taught binary. I'm not so sure about this one.
posted by notsnot at 9:31 AM on September 12, 2004

oh, but i have to ask - given that scheme, what's the upper bound on the number of representations for n as n->inf?
posted by andrew cooke at 9:33 AM on September 12, 2004

What, on the number of redundant representations? I think it's boundless!

Maybe I'll go back to grad school and take up a project on this...
posted by notsnot at 9:36 AM on September 12, 2004

I just got an IM with a Fibonacci base explanation (called Fibonaccimal or the Zeckendorf representation) which makes it seem that a prime base is possible, if not practical. The author addresses the problem with numbers having multiple representations by deciding that "no two consecutive Fibonacci numbers can be used in the same sum."

And no, I have no idea why you would want to use a base prime system, unless you found it easier to write a 1 followed by 100 zeros than figuring out the hundredth prime.
posted by revgeorge at 9:41 AM on September 12, 2004

i meant as a function of n - sorry, don't know correct terminology
posted by andrew cooke at 9:43 AM on September 12, 2004

ah, no i don't think it's interesting anyway - i was confusing additional and multiplication...
posted by andrew cooke at 9:53 AM on September 12, 2004

Oh and It's Dog, not bear. I must have had this bear in mind from the Googling I did
posted by revgeorge at 10:06 AM on September 12, 2004

1 is not prime, and is pretty essential for representing quantities, so the answer to your question as given is no. Primes are also, by definition, all positive, so you'd be excluding the possibility of expressing negative numbers.

But just to consider positive integers, and If we throw 1 in with the primes, your question becomes "Can every quantity be expressed as the sum of products of members of the set containing 1 and the prime numbers?" 4 = 2 x 2, 6 = 2 x 3, 8 = 5 + 3, 9 = 3 x 3, 10 = 2 x 5... as soon as we hit a quantity we couldn't represent this way, we'd know the answer was no.

It's easy to represent relatively small quantities this way, 'cause there are so many building blocks nearby. There are even multiple ways to express some equivalent quantities, which might be considered a drawback to a counting system. 28 = 11 + 17. Or 17 + 5 + 2 x 3. Or 2 x 11 + 2 x 3...

My suspicion, which I'm not going to try to prove, is that with large numbers, where there are a lot of numbers between primes, you'd find something you couldn't express.

Further, one of the nice things about base n is that you need only n labels to represent your digits. Needing an infinite number of labels would be a pretty severe drawback.
posted by Zed_Lopez at 10:13 AM on September 12, 2004

My suspicion, which I'm not going to try to prove, is that with large numbers, where there are a lot of numbers between primes, you'd find something you couldn't express.

with traditional systems the increase in weight with place is exponential (eg decimal, 10^n). so you need to get larger gaps than that to be worried. primes aren't that scarce (still can't remember the distribution but it's so famous you must know it).
posted by andrew cooke at 12:58 PM on September 12, 2004

Zed,

all integers can be expressed as the product of primes. That's the Fundamental Theorem of Arithmetic. You can think of this intuitively when you think about the definition of a prime number. A prime number is any number which is divisible only by itself and 1.

So if you find a number which can't be expressed as the product of primes then you've got a prime number. You don't need a sum of products to express an integer, you only need a chain of products.
posted by substrate at 1:37 PM on September 12, 2004

primes aren't that scarce (still can't remember the distribution but it's so famous you must know it).

Number of primes less than n is about n/ln(n), but is even closer to int(1/ln(x) dx, 2 to n).
posted by j.edwards at 1:47 PM on September 12, 2004

oooh! decimals (values to the left of the decimal point, not based ten numbers) are interesting in this system - especially if you allow lots of "digits". you can represent any rational number, given enough decimal places. :o)
i guess i'm stating the obvious (or i'm wrong), but it just struck me....
posted by andrew cooke at 2:38 PM on September 12, 2004

It has been conjectured (but not proven) that under your system, every even number greater than two can be expressed by a number having the sum of its digits equal to 2. This is just Goldbach's conjecture translated into this weird-ass system. If this were true, it would also follow that any odd number would be expressible by a number having the sum of its digits 3 or less.
posted by Johnny Assay at 3:22 PM on September 12, 2004

What I thought of by a prime-base number system was one where the factor each place was multiplied by was a prime number - so the value of each place would be 1, then 2, then 6 (2x3), then 30 (2x3x5), then 210 (2x3x5x7) and so on. Counting would look like this: 1 10 11 20 21 100 101 110 110 120 121 200 201 (blah blah) 300 301...321 400 401...421 1000. The maximum digit in each place would be the next higher place minus one (which means that once you got into the 210s place, you'd need an "A" digit for 10 210s before you got up to 2310 (2x3x5x7x11)).
posted by wanderingmind at 6:09 PM on September 12, 2004

I'm not sure if your original idea works or not revgeorge, but it would make for some bizarre arithmetic rules. Basically you'd need to always know all the primes up to whatever the number of significant primes in your number is in order to even do addition.

There's no canonical representation for a number either which isn't fatal.

For any number that can be represented though you could come up with a representation that looks like a binary string (sort of like your sequence above), so you'd just see a string of ones and zeros.

To see the weirdness consider a couple of numbers in the binary-like representation:

01100111 and 00100001.

Each column, from left to right represents 13s, 11s, 7s, 5s, 3s, 2s and 1s (which aren't prime but have to be thrown in or you throw out half the possible numbers)

0 1 1 0 0 1 0 1
0 0 1 0 0 0 0 1
-------------------
0 1 2 0 0 1 0 2

Now to make it fit back into the binary like representation some
carries need to be made.

0 1 2 0 0 1 0 2, the rightmost column are ones, and a pair of ones makes two which is prime:

0 1 2 0 0 1 1 0, the 3rd column represents 7s, so a pair of 7s is 14 and that's 1 in the 13s column and 1 in the 1s column:

1 1 0 0 0 1 1 1

With ordinary base-N numbers we know that if two digits are summed and greater or equal than N we carry. How do you define that for a base-prime representation? I chose to represent numbers so that each prime was either present or not present in the composite number. Other rules could be done but regardless you need to know the next prime in order to do your carries.

As far as if it's a possible number system you'd have to consider the possibility that up to some prime P0 there is a way to represent every composite number up to P0-1. The next prime after P0, P1, would have to be less than 2*P0 in order to have complete coverage.

N factorial + 1 (N! + 1) is always prime though it isn't every prime. This doesn't guarantee that the binary-like prime system doesn't work but it doesn't prove that it'll work either.

If there was a stretch between two primes described by N!+1 such that there were only composite (non-prime) numbers between it then:

P0 = N! + 1
P1 = (N+1)! + 1

the ratio between P0 and P1 will be approximately N+1, so
you could guarantee that your system would work if you allowed each digit in your representation to reach N+1.

There are probably other "follow this formula and you'll always get a prime" that narrows this range though. I doubt if the binary-like representation can work but there's probably some acceptable compromise.
posted by substrate at 8:30 PM on September 12, 2004

One interesting point, redundant number systems are often exploited because they allow you to do arithmetic without doing carries. Carries are slow because they can break addition down into a sequential operation. Add 1 to 99999999 base 10 and you'll see what I mean. The prime base system isn't immune from carries though so it's a redundant system but the redundancy doesn't help you in any way.
posted by substrate at 8:34 PM on September 12, 2004

Hmm... I am wrong. N! + 1 isn't always prime though I had heard that it was. Sorry.
posted by substrate at 5:36 AM on September 13, 2004

you're thinking of the product of all primes up to some value plus one - it's from the proof that there are an infinite number of primes.

i was wrong about the fractions.
posted by andrew cooke at 6:00 AM on September 13, 2004