Counting in Base and Prime Numbers

Whilst counting in a bases, it becomes apparent that some numbers are not prime. I.e. Any numbers ending in 2, 5 and 0 whilst counting in base 10.

This is because counting in base is a form of arithmetic.

Let's take base 10. It is divisible by 2 and 5. Hence the non-primes above. But also 4, 6 and 8, multiples of 2 smaller the 10.

Counting in base 3, you can only see numbers ending in 0 as being non-primes.

It appears that there is a correlation between number base systems and prime numbers (or non-prime numbers).

Based on the fact that these base systems seem to be linked, but in a rather limited way. For each number base being used, you can tell only the numbers which the base is divisible by. In this sense, the best base to work in is one which is divisible by many prime numbers.

e.g.

2x3=6

2x3x5=30

...

2x3x5x7x9x11=20790

This doesn’t seem very efficient. But perhaps we can improve things.

But first I want to discuss the point in using base systems. Surely all we need is an equation to work out prime numbers? Yes, but we have yet to find one which works efficiently with computing.

Hence investigating the base system, which is what humans and computers use to work these things out. Humans (mostly) in base 10, and (most) computers in base 2 (binary)

My thoughts were guided onto the idea of a new base system which relied on only prime numbers. The uniqueness of prime numbers is a good starting point. All numbers are either prime or not, and those that aren’t can be represented in terms of prime numbers. So in theory we don’t need to represent these numbers. Here is the initial number system idea, non-primes are represented as their prime factors (but using Base Prime) separated with a comma:

Base 10	Base 2	Base Prime
1	1	1
2	10	2
3	11	3
4	100	2,2
5	101	4
6	110	2,3
7	111	5
8	1000	2,2,2
9	1001	3,3
10	1010	2,4
11	1011	6

In base prime you can write any number down and immediately see if it is prime or not.

e.g.

4 is prime

5  is prime

10 is prime

2,2 is not prime

3,6,8 is not prime

100000000000 is prime!

The only problem (at the moment) is the fact that it is hard to work out what that number is in any ‘normal’ base system. i.e.

1 = 1

2 = 2

3 = 3

2,2 = 4

4 = 5

10000000000000 = ?????

What we need is a way of converting, but not algorithmically but logically, as this is how computers compute!

To do this I propose we must be able to do arithmetic using this new system. Once this can be done, we will be able to convert to other base systems.

e.g.

1+1 = 2

2+1 = 3

2+2 = 2,2
3+1 = 2,2
3+2 = 4

3+3 = 2,3
4+1 = 2,3
4+2 = 5
4+3 = 2,2,2

4+4 = 2,2,2

5+1 = 2,2,2
5+2 = 3,3
5+3 = 2,4
5+4 = 3,3
5+5 = 2,5

Arithmetic is the utilisation of patterns apparent in the number system being used.

One such pattern I've seen is the doubling of prime numbers:
1+1 = 2
2+2 = 2,2
3+3 = 2,3

4+4 = 2,4
5+5 = 2,5
6+6 = 2,6
7+7 = 2,7
8+8 = 2,8

Adding to itself is another way of saying 2x. This could be utilised for arithmetic.

A more obvious pattern is the use of multiplication.
1x1 = 1
2x2 = 2,2
3x2 = 3,2
3x3 = 3,3
4x2 = 4,2
4x3 = 4,3
4x4 = 4,4

2,2x2 = 2,2,2
3,4x4 = 3,4,4

Another question might be how to do arithmetic with non-primes?
2,2+1 = 4
2,3+1 = 5
2,2,2+1 = 3,3

For the moment I can see no pattern, but adding one to a number is very important thing to do! But I think we need to keep looking for patterns.

It appears that adding 1 is a difficult thing to do. I think this is because all other numbers, including primes, are divisible by two numbers, itself and 1, but 1 is only divisible by 1 thing. This makes it one of the uniques numbers, others being 0 and minus numbers. Perhaps it should be represented using another form. It can take the form: x/x where x is another number in the equation. e.g.

2,2 + 1 = 2,2 + (2,2 /2,2)

also, if we choose not to represent 1, we could use this figure to represent the first prime number 2₁₀

The same could also apply to 0₁₀ , which could be represented as x-x, e.g.

2,2 + 0 = 2,2 + 2,2 - 2,2

I think it's a valid thing to think about.

After playing with the Base Prime system there are some key points/questions I'd like to make:

• In Base systems, the order you write the numbers is important. It doesn't appear to be important here? Should there be a system for the order in which you write the numbers? Perhaps smallest first?
• It's hard to know what to do with the squares and cubes? for the time being I prefer to write all the numbers down. e.g. 8₁₀=2,2,2. Although it could be 2³

C Programming - convert number to any base

Just to continue with my programming practice I decided to write a function which takes a number and a base and converts that number to that base.

Here's the function:

//takes a number and a base to work to. It converts (just prints) this number to said base

//base has to be greater then 1

void printInBase(int number, int base) {

    

    assert(base > 1);

    

//find out how many units is needed to make the number

//int numberOfUnits = 1;

int units = base;

while (units <= number) {

//numberOfUnits ++;

units = units * base;

}

    //make an array which will be printed out in the end

    //int numberArray [numberOfUnits];

//work out which how many of each unit

    //int i = 0;

    

int result = number;

while (units > 1) {

units = units / base;

printf("%d", result / units);

result = result % units;

        //i++;

}

 

//prints out array

    //for (int c = 0; c <= numberOfUnits ; c++) {

    //    printf("%d", numberArray[c]);

    //}

}

 Output:

Type a starting number: 1

Type an end number: 30

Type a base to count in: 7

1 = 1

2 = 2

3 = 3

4 = 4

5 = 5

6 = 6

7 = 10

8 = 11

9 = 12

10 = 13

11 = 14

12 = 15

13 = 16

14 = 20

15 = 21

16 = 22

17 = 23

18 = 24

19 = 25

20 = 26

21 = 30

22 = 31

23 = 32

24 = 33

25 = 34

26 = 35

27 = 36

28 = 40

29 = 41

30 = 42

The function fails at counting base 1, but it hurts my brain too much to think about it! Also, to count in a base larger then 10, it's best to put a comma between digits. e.g:

Type a starting number: 1

Type an end number: 30

Type a base to count in: 15

1 = 1,

2 = 2,

3 = 3,

4 = 4,

5 = 5,

6 = 6,

7 = 7,

8 = 8,

9 = 9,

10 = 10,

11 = 11,

12 = 12,

13 = 13,

14 = 14,

15 = 1,0,

16 = 1,1,

17 = 1,2,

18 = 1,3,

19 = 1,4,

20 = 1,5,

21 = 1,6,

22 = 1,7,

23 = 1,8,

24 = 1,9,

25 = 1,10,

26 = 1,11,

27 = 1,12,

28 = 1,13,

29 = 1,14,

30 = 2,0,

This way you can distinguish between the 10's and 20's etc. Might be worth putting this in the function. But also, I could make it convert to hexadecimal? Might require more brain hurt.

Finding Prime Numbers

Thought I'd test out some programming I'd learnt so I'm now writing a program to find large prime numbers. Here's the basic program which I'll improve over time:


main()
function main () {
    print ("hello");
    printPrimeNumbers (1, 100);
    return 0;
    }

function printPrimeNumbers (startNumber, maxNumber) {
    var counter = startNumber;
    while (counter < maxNumber){
        if (isPrime(counter)) {
            print (counter);
            }
        counter++;
        }
    return 0;
    }

function isPrime (number) {
    var prime = true;
    if (number > 3){
        if (number !== 0){
            var i = (number-1)/2;
            while (i>1) {
                if (number % i == 0) {
                    prime = false;
                    return prime;
                    }
                    i--;
            }
        }
         else {
                prime = false;
                }
    }
    return prime;
    }

Basically, isPrime (number) is the function which is doing all the work at the moment. If the number is greater then 3 and not divisible by 2 then: see if it can be divided by any number smaller then itself. This number starts from itself divided by two to reduce the number.

Found this little site which gives nice little examples of small C programs

So far this works. It is in fact already optimised slightly with the:
 if (number !== 0)
and
var i = (number-1)/2;

I havent actually read up on any optimisations anyone else has done. I think I'll carry on and when I get stuck I'll do some research.

My next main idea is to record all prime numbers starting from one up to the maxNumber. Then, to find out if the next one is a prime, just divide by all other primes before it. Should then not have to do as much work, perhaps by 3/4? The two down sides are that:

1. I'd have to store these numbers somewhere
2. I'd have to have all the primes up to the number you want to know whether is a prime or not.

Heres the script I came up with in C:

#include

#define true 1

#define false 0

#define STARTNUM 1

#define ENDNUM 100000000

int printPrimes (int startNumber, int maxNumber);

int isPrime (int number, int primesArray[], int numberOfPrimes);

int main (int argc, const char * argv[]) {

    printf ("hello \n");

printPrimes (STARTNUM, ENDNUM);

    return 0;

}

int printPrimes (int startNumber, int maxNumber) {

    int counter = startNumber;

int numberOfPrimes = 0;

int primesArray [100000];

    while (counter < maxNumber){

        if (isPrime(counter, primesArray, numberOfPrimes)) {

            printf ("%d\n" , counter);

primesArray[numberOfPrimes] = counter;

numberOfPrimes++;

}

        counter++;

}

/*printf("Printing the Array of Primes\n");

for (int c = 0; c < numberOfPrimes; c++) {

printf("%d\n", primesArray[c]);

}*/

    return 0;

}

int isPrime (int number, int primesArray[], int numberOfPrimes) {

    int prime = true;

    if (number <= 3){

            for (int i=1; i

if (number % primesArray[i] == 0) {

                    prime = false;

                    return prime;

}

}

    }

    return prime;

}

Works pretty well.

A future idea is to find the frequency of primes and find a relationship. Perhaps taking it one step further and finding the frequency of frequencies. I'm not sure how to represent frequencies though?