Question

A number can be represented as a product of prime numbers or as a sum of coefficients on a basis raised to powers, for example: \[\Large 15 = 2^03^15^1=5*10^0 + 1*10^1+0*10^2\]

Answer 1

So in general we can represent any number n like this: \[\Large n=p_0^{x_0}p_1^{x_1}p_2^{x_2}...\]\[\Large n=x_0b^0+x_1b^1+x_2b^2+...\] For what numbers in what base number system are all the x's exactly the same? For example, 3 and 12 work, 12 in base 10 and 3 in base 3.

\[\Large 12= 2^2*3^1=2*10^0 + 1*10^1\]
\[\Large 3= 2^0*3^1=0*3^0 + 1*3^1\]

Answer 2

So far the numbers that I've found that work out are 0, 3, 6, 10, 12. And if you allow for noninteger basis you can get a couple others in there as well, the general formula for prime numbers is: \[\Large b=\sqrt[n]{p_n}\] So we can see this explains the 3 case pretty well.

My general approach so far is to get its prime factorization and solve the resulting polynomial for the base, so for example: \[\Large 10 = 2^13^05^1=1b^0+0b^1+1b^2\] \[\Large 1b^0+0b^1+1b^2 = 10 \\ \Large 1 + b^2 =10 \\ \Large b =3\] So plug it back in to check: \[\Large 10 = 1*3^0 + 0*3^1 + 1*3^2 \\ \Large 10 =1+0+9\] Cool ok lol.

Answer 3

Here's a handy list that even tells you that 2 is the 0th prime and not the first, so it's indexed appropriately! http://faculty.kutztown.edu/rieksts/OLD/341-F03/projects/ca-crypt/primes.html

Answer 4

So for instance if we wanted to see if 5723 had an integer basis that worked, we could factor it and look up the prime factors to see: \[\Large 5723 = 59^1*97^1= 1*b^{16}+1*b^{24} = 5723\] noting that the other weights on the basis will be zero, we can just exclude them to try to solve. Unfortunately it doesn't look like it has an integer solution: http://www.wolframalpha.com/input/?i=+b%5E16%2Bb%5E24+%3D+5723

Answer 5

There is no prime factorization for \(0\) though.

Answer 6

Interestingly, the next number after 12 is 24 in the sequence.

3, 6, 10, 12, 24

For some reason they are following a peculiar looking pattern.

Also, you're right there is no prime factorization of 0 lol I don't know what I was thinking haha.

Answer 7

If you are given some integer and its prime factorization, will it always be possible to find a basis that will give you a result you want?

Answer 8

My impression is that you won't be able to.

Answer 9

Nope, I think I worked out an example above where it fails. What you are describing are essentially the "holes" in the sequence 3, 6, 10, 12, 24, ...

Answer 10

For \(3\) wouldn't the basis be \(3\)?

Answer 11

That list of primes you found is quite nice, and an excellent reference.

Answer 12

It is indeed. In fact you can show that 3 is the only prime number to an exponent that can be expressed this way.

Answer 13

So let p be the nth prime and m is the exponent, so for instance 25 would be \[\Large 125 = p_2^3\]Remember, we start counting primes at 0 so 5 is really the 2nd prime after 2 and 3 the 0th and 1st primes. Ok now to the formula:\[\Large p_n^m=mb^n\] The left is the number represented as the prime factorization and here it is in the basis summation on the right. We don't know the basis yet, but we know it has coefficient m and that in this basis it has the nth powers ince all the other basis have 0 as their coefficients.

Since this is a prime number, m and b have to be powers of p_n so we replace: \[\large m=p_n^k \\ \large b=p_n\] but this isn't entirely right. m hast to be smaller than b, otherwise it would be the coefficient on a higher power. It would be like saying 100 is really 0*1+10*10 which putting the 10 in the tens place rather than 0*1+0*10+1*100 which is the correct way of placing them, so we know that since m has to be a power of the prime, that k has to be equal to 0 since when k=1 it is not placed correctly.

\[\large m=1 \\ \large b=p_n\] Now if we plug this into the formula we had before: \[\Large p_n^m = mb^n \\ \Large p_n^1=p_n^n \\ \Large p_1^1=3\] So 3 is the only prime raised to any exponent on its own that satisfies this.

So we can compare that 3 in base 3 is 10 and the exponent vectors we described befre are also <0,1> which is really just the reversed order of how we write the number in base 3, which is how you should probably think about these problems in general.

Answer 14

This is all my own thing as far as I know, everything you see I've just sort of figured out in the past hour lol. I don't know, I feel like it's a step in the right direction and it seems like there might be some slight connection to using exponents on primes as a vector space as well as the arithmetic derivative. Just playing around and having fun for now ahaha

Answer 15

I think the fact that in one case you're adding up, and in another case your multiplying up makes it all sort of patternless.

Answer 16

Just as patternless as primes as far as I can tell.

Answer 17

I will believe it's not a real pattern though if you can prove that there are a finite number of these haha =P

Answer 18

Could you show the example you worked out in which it fails?

Answer 19

@Jhannybean I just copied this from earlier, you can use that primes list I put earlier to check this. It might make more sense if you try to work out a smaller problem first though since it might seem a little abstract by how large this number is:

So for instance if we wanted to see if 5723 had an integer basis that worked, we could factor it and look up the prime factors to see: \[\Large 5723 = 59^1*97^1= 1*b^{16}+1*b^{24} = 5723\] noting that the other weights on the basis will be zero, we can just exclude them to try to solve. Unfortunately it doesn't look like it has an integer solution: http://www.wolframalpha.com/input/?i=+b%5E16%2Bb%5E24+%3D+5723

Answer 20

I'll work out a smaller problem where it fails. \[\Large 18=2^13^05^2 = 1b^0+0b^1+2b^2\] So the key point is that the exponents on the left are the coefficients on the right. The exponents on the right however are consecutive integers while the primes on the left are consecutive primes. So this is the connection here. Now we can try to solve for the basis using these: \[\Large 18 = 1b^0+0b^1+2b^2 \\ \Large 18=1+2b^2 \\ \Large 17=2b^2 \\ \Large \frac{17}{2}=b^2 \\ \Large \pm \sqrt{\frac{17}{2}}=b \]

So since this isn't a positive integer, we can't represent this in a regular basis unfortunately like we can represent 3 in base 3 as 10. or 24 in base 21 as 13.

Answer 21

A simplification might be to write them like this: \[\LARGE 24 = 7^05^03^1 2^3 = 0013_{21}\] The problem is that digits are written in descending order so it looks weird. I put the extra two leading zeroes just to show they are analagous. You can add infinitely many larger prime numbers with 0 exponents just like you can add infinitely many 0s in front of a number without changing it.

Answer 22

More nonsense, but in a lot of ways what I'm striving for is really looking at special cases where there is a kind of relationship between the prime factorization and expansion of basis.

To me, this is similar to the pattern of representing a vector as either in rectangular or polar form. It's kind of like: \[\Large z= re^{i \theta} = a+bi\]

Answer 23

Hmmm

Answer 24

Which corresponds to which?

Answer 25

Here is my vague analogy

\[\Large z= re^{i \theta} = a+bi\] \[\Large 6 = 3^12^1 = 1*5^0+1*5^1\]

Answer 26

I guess I don't need to decompose them in this way, maybe I need to look for a different connection something like: \[\Large a = p^xq^y = m *b^0 + n*b^1\] so from this maybe I can deduce like a length or something from it, \[ \Large m^2+n^2= ? \] just like we have \[\Large r^2=x^2+y^2 \] but different. Ok, this is probably a dream but if it exists it would be awesome haha.

Answer 27

Yeah I'm kinda out of ideas atm but I am trying to look at how the basis can be changed and considering what a basis of 1 means (well, nothing really) but it gives me a starting point of an extreme to consider I suppose.

Answer 28

I'm gonna go eat dinner, but if you're both still interested in playing around, maybe aranging them in a table like this will help you:
\[\Large 2 = 10_2 = 2_{3+} \\ \Large 3 = 11_2 = 10_3 = 3_{4+} \\ \Large 4 = 100_2=11_3 = 10_4 = 4_{5+} \\ \Large 5 = 101_2 = 12_3 = 11_4=10_5=5_{6+} \\ \Large ...\]

Answer 29

Certain bases are easier to convert to others.

Answer 30

A base is easily converted to another if you can convert \(n\) digits into \(m\) digits in the other base.

Answer 31

That ends up being \(O(n)\).

Answer 32

Otherwise, you have to do a bunch of modulus and division operations.

Answer 33

Here is a revised table for me to look at in case there might be a pattern in it.
\[\Large 0 = 0_{1+} \\ \Large 1 = 1_{1+} \\ \Large 2 = 10_2 = 2_{3+} \\ \Large 3 = 11_2 = 10_3 = 3_{4+} \\ \Large 4 = 100_2=11_3 = 10_4 = 4_{5+} \\ \Large 5 = 101_2 = 12_3 = 11_4=10_5=5_{6+} \\ \Large ...\]

In a way I kind of see that there is a kind of circularity of definition of i in \[\Large i = e^{i \frac{\pi}{2}}\] which is similar in a way to expressing a number in its basis.\[\Large 10 = 0*10^0 + 1*10^1\]

Taking the complex number a little further, we have: \[\Large e^{i \frac{\pi}{2} }= 0*i^0+1*i^1\] It is temptingly similar in a lot of ways. But maybe I'm just wishful thinking here.

Answer 34

That's just because: \[b = 0b^0+1b^1\]

Answer 35

Due to the was bases work, you can't have a digit higher than the base.

Answer 36

Sure, but it's just an analogy I'm not saying there is some kind of mapping to complex numbers or anything. I'm just saying there might be a relationship that is equivalent to relating a basis to its prime factorization and vice versa just like: \[\Large r = \sqrt{x^2+y^2} \\ \Large \theta = \arctan(\frac{y}{x})\]