First Post on Primes

[Tinacity]

Hi everyone.

Tina here. This is my first ever post on such a forum and would apologise in advance for my lack of formal clarity and perhaps very amateurish presentation etc.

 

But I have a burgeoning interest in the beautiful mystery and potential of mathematics and reason in general.

 

And would love that anyone might direct me in my latest field of curiosity, which is....well...."things to do with primes."

 

I may not be able to formalise my question very well....as intimated....and do understand in general that people often may not even be sure what they are asking..

 

But here goes....

 

Consider, if you would.....the number 2*3*5*7*11*13*17*19*23 = 223092870 ( the product of the first 9 primes).. Call this number: N

 

Firstly. Am I correct in assuming that there are 3*5*9*11*15*17*21 pairs of numbers which can be summed to make N, where neither is divisible by any of the primes which make its product? Call that X

 

If so....what is the mathematical reference to this fact? Is this related to both the Chinese Number Theorem and something called Euler's totient? (yes...I am a bit of a math noob, but I will learn)

 

Secondly: Is it the case that there is also the same number of numbers X which are also divisible by 2? Call this XE

 

I am mainly interested in how to determine how many pairs XE, are also divisible by some other number, such as 29 or 16 for example.....

 

What is the math for predicting that kind of thing?

 

Thank you so much in advance for you tolerance of this relative intrusion into a formalised world with a less than formal approach and presentation.

 

Tina

 

 

Edited October 28, 2020 by Tinacity
Forgot that X cannot be divisible by 16 as it isn't even...but XE is even.

[Tinacity]

Have I said something too stupid? Is the answer too simple?

 

Just a simple division?

[StringJunky]

@studiot @joigus @wtf See if one these guys can help.

Edited October 30, 2020 by StringJunky

[joigus]

On 10/28/2020 at 4:26 PM, Tinacity said:

What is the math for predicting that kind of thing?

The maths for predicting that kind of thing is called number theory. I know very little about number theory. It studies connections between numbers.

The result that you propose reminds me of some theorems by Fermat. Have you proved it, or is it just an intuition?

Maybe @wtf or @Sensei, or @mathematic, or @taeto can help you. @studiot is encyclopedic. Maybe he can help you too.

Number theory is not very interesting for physics, AFAIK. And physics and mathematical physics are my turf.

 

[Sensei]

On 10/28/2020 at 4:26 PM, Tinacity said:

Firstly. Am I correct in assuming that there are 3*5*9*11*15*17*21 pairs of numbers which can be summed to make N, where neither is divisible by any of the primes which make its product? Call that X

No. You're not correct. There is actually infinite quantity of pairs which summed together will give you other number.

e.g. how many pair of numbers will give you 2?

1+1=2 (obvious answer)

-1+3=2 (ha!)

-2+4=2

etc.etc.

Also e.g. rational and irrational numbers can sum to 2..

0.5+1.5=2 (ha!)

1.9+0.1=2

etc. etc.

You didn't specify that only positive integers between 0...N are accepted as answers..

You didn't specify whether 0 is excluded or included in the considerations.

Edited October 30, 2020 by Sensei

[joigus]

1 hour ago, Sensei said:

You didn't specify that only positive integers between 0...N are accepted as answers..

 

She didn't specify, but I thought it was kind of implied...

For arbitrary products of primes, certainly nothing like that can be proved with the present mathematics. But for 223092870, I just don't know.

[ahmet]

as far as I remember , chinese remainder theorem and euler theorem (also fermat) are relevant to congruences. (to calculate residues)

 

4 hours ago, Tinacity said:

Have I said something too stupid? Is the answer too simple?

 

Just a simple division?

I recommend that you write something mathematically meaningful.

you may apply or appeal to some general theorems or propositions or you can refer to some axioms. 

 

Edited October 30, 2020 by ahmet

[Tinacity]

I appreciate your response Ahmet......It's tricky for newbs, I guess, to participate sensibly.....

[studiot]

I did look at this one, but I am sorry to say that all of us have parts of our subject we like more than other parts.
And  amongst my personally least liked parts are combinatoric and number theory.

There seem to be several problems of this type going around at the moment.

On another (maths) forum they have been debating this simpler one for a couple of weeks now.

Quote

Using the digits 1-8 how many different ways can the digits be arranged to make 2 numbers whose sum is 9999.

and this is only  a four digit number.

The one here is a nine digit number so I would expect candidate numbers for addition to be of the form  xxxxxxxxx  +  yyyyyyyyy

Which has a lot more combinations.

This really is problem that lends itself to a computer solution so I am suprised at Sensei's response, which is incorrect.

since the last digit is a zero, there must be a carry so possible choices for pairs in the last positions are [0,0}, {9,1} , {8,2}. {7,3), {6,4} and {5,5}

So {x,y} can be selected in 6 different ways.

But any number ending in a 5 is divisible by five so the last one can be discounted.

Further reduction can be had by noting that any pair containing an even number can be discounted as divisible by 2, another orignal factor.

You can work through the digit pairs to find out how many possibilities there are for each other pair.
Then multiply these together an see the final result, using the laws of combinatorics.

On 10/28/2020 at 3:26 PM, Tinacity said:

Firstly. Am I correct in assuming that there are 3*5*9*11*15*17*21

 

Tina please note this first result and compare with your answer.

 

 

2 hours ago, Sensei said:

Also e.g. rational and irrational numbers can sum to 2..

0.5+1.5=2 (ha!)

1.9+0.1=2

I don't think there are any two irrational numbers that can be added together to make a rational one.
In any case none of these are irrational.

 

 

Edited October 30, 2020 by studiot

[joigus]

Now that I think about it, the product of the first 23 is, as you say, 223092870.

Now, the number of ways in which you can sum two (arbitrary) natural numbers to give N is just 111'546'435, because 223'092'870 is even.

So the problem reduces to finding how many numbers there are between 1 and 111'546'435 that are not divided by 1, 2, 3, 5, ..., 23 (the 1st 23 primes).

The only thing I can say is that's not an elementary problem. How did you get your conjecture @Tinacity?

15 minutes ago, studiot said:

I don't think there are any two irrational numbers that can be added together to make a rational one.

Counterexample: \( \pi \) is irrational; \( 1-\pi \) is irrational too. but \( \pi + 1- \pi = 1 \).

[studiot]

4 minutes ago, joigus said:

22 minutes ago, studiot said:

I don't think there are any two irrational numbers that can be added together to make a rational one.

Counterexample: π is irrational; 1−π is irrational too. but π+1−π=1 .

Nice one.  +1

[Sensei]

9 hours ago, studiot said:

This really is problem that lends itself to a computer solution so I am suprised at Sensei's response, which is incorrect.

I am surprised by your comment. Mathematics is strict discipline. I was just pointing out that she should say "natural numbers" rather than "numbers".

 

9 hours ago, studiot said:

I don't think there are any two irrational numbers that can be added together to make a rational one.

I was just going to say it is not true, but see @joigus already did it for me..

[joigus]

11 hours ago, joigus said:

So the problem reduces to finding how many numbers there are between 1 and 111'546'435 that are not divided by 1, 2, 3, 5, ..., 23 (the 1st 23 primes).

Sorry, the problem reduces to how many numbers there are between 1 and 223'092'869 that are not divided by 1, 2, 3, 5, ..., 23.

[ahmet]

12 hours ago, joigus said:

 

Counterexample: π is irrational; 1−π is irrational too. but π+1−π=1 .

I remember one  expert (associate professor) in algebra (now he is professor) was using a sentence like this

 

"Ahmet do you know, I sometimes think whether a couple of  rational and irrational numbers are summable, do you think that these are summable?"

now my answer is that "I doubt".

 

Edited October 31, 2020 by ahmet

[joigus]

1 hour ago, ahmet said:

I remember one  expert (associate professor) in algebra (now he is professor) was using a sentence like this

 

"Ahmet do you know, I sometimes think whether a couple of  rational and irrational numbers are summable, do you think that these are summable?"

now my answer is that "I doubt".

 

Why wouldn't rational and irrational numbers be summable?

[studiot]

4 hours ago, Sensei said:

I am surprised by your comment. Mathematics is strict discipline. I was just pointing out that she should say "natural numbers" rather than "numbers".

Why are you suprised?

Yes, you made a valid comment that the problem is ill defined.

But you also made an invalid one about irrational numbers in your examples.

Yes I also made an invalid one, which joigus picked up and I immediately corrected.
We all make mistakes; we all need to admit them.

2 hours ago, joigus said:

Sorry, the problem reduces to how many numbers there are between 1 and 223'092'869 that are not divided by 1, 2, 3, 5, ..., 23.

Well this is one very long way to do it since that is only a beginning, not a solution.

There are plenty of primes less than your criterion for example the 1,000th prime is only 7919

Further there are other non prime numbers not divisible by your set eg 2419 is not prime nor divisible by your set.

[ahmet]

12 minutes ago, joigus said:

Why wouldn't rational and irrational numbers be summable?

not sure but because (for first check), irrational numbers are in fact, the consistence of their existence (they exist,ok no problem with this part. But not applicable)

in general,you cannot write any irrational number in the form of rational. Otherwsie, if you try to do so,then  you will not be able to conclude the operation. 

the operation will extend to infinity,which causes not to make conclusion for the operation. 

Thus ,those two kinds of numbers,to me, are not summable.

however, there might be more contexts which could be reference for this.

Edited October 31, 2020 by ahmet

[joigus]

2 minutes ago, studiot said:

Yes I also made an invalid one, which joigus picked up and I immediately corrected.
We all make mistakes; we all need to admit them.

You guys are very valuable members of this community. I've been swept away by both of you several times.

4 minutes ago, studiot said:

There are plenty of primes less than your criterion for example the 1,000th prime is only 7919

Yes, you're right, @studiot. But the OP was about the very special, very non-prime number \( 2\cdot3\cdot5\cdot7\cdot11\cdot13\cdot17\cdot19\cdot23 \), factor of the first 9 prime numbers.

[studiot]

31 minutes ago, joigus said:

 

Yes, you're right, @studiot. But the OP was about the very special, very non-prime number 2⋅3⋅5⋅7⋅11⋅13⋅17⋅19⋅23 , factor of the first 9 prime numbers.

The point is that  prime no prime number greater than 23 is divisible by any of the first 9 primes.

So each prime number and its pair which adds to make  223092870 will be candidates for inclusion and so must be checked.

and there are a great many prime numbers up to 9 digits long.

But added to these are numbers which are not prime yet still not divisible by any of the first 9 primes such as the example 2419 I gave.

All of these must also be checked.

[Tinacity]

I truly respect and appreciate everyone's contribution.

And would apologise for my lack of rigor and formality in defining the problem space.

 

Yes....I am only refering to the set of natural numbers in this problem space.

And I wanted to assume that the number of pairs which sum to N are given by the product: (3-2)*(5-2)*(7-2)*(11-2)*(13-2)*(17-2)*(19-2)*(23-2) and to have that confirmed if possible.

Then I wanted to assume that there were an equal number of pairs where the pair members are also divisible by 2. 

And that this number of pairs, I perhaps clumsily called XE, is my main ongoing focus.

And examining the pairs of XE....And whether any member of each pair is exactly divisible by some given natural number.And how many there are.

I chose 29 and 16 as examples.....but, again, hoping to generalise on any result.

Noting that brute force calculation is not what I am looking for....as I want to generalise any result if possible.

I hope that fills some of the gaps in my clumsiness.

 

 

 

Edited October 31, 2020 by Tinacity

[Sensei]

17 hours ago, studiot said:

This really is problem that lends itself to a computer solution...

Yesterday, it was too late. OK. Now, I made program in C/C++:

#include <stdio.h>

//int primes[] = { 2, 3, 5, -1 };
int primes[] = { 2, 3, 5, 7, 11, 13, 17, 19, 23, -1 };

bool check(int a, int b) {
	for (int i = 0; primes[i] > 0; i++) {
		if ((a % primes[i]) == 0) return(false);
		if ((b % primes[i]) == 0) return(false);
	}
	return(true);
}

int main(int argc, int *argv[]) {
	int count = 0;
	int end = 1;
	printf("Primes: ");
	for (int i = 0; primes[i] > 0; i++) {
		printf("%d ", primes[i]);
		end *= primes[i];
	}
	printf("\n");
	printf("End %d\n", end);
	int half = end / 2;
	for (int i = 0; i < half; i++) {
		int a = i;
		int b = end - a;
		if (check(a, b)) {
			//printf("Found %d %d\n", a, b);
			count++;
		}
	}
	printf("Count %d\n", count);
	return(0);
}

For test case with 3 primes it gave:

Quote

Primes: 2 3 5
End 30
Found 1 29
Found 7 23
Found 11 19
Found 13 17
Count 4

Which looks good.

For OP problem with 9 primes it gave too many results to show them all (so had to disable printf()):

Quote

Primes: 2 3 5 7 11 13 17 19 23
End 223092870
Count 18247680

18 mln is over twice more than OP value.

[joigus]

1 hour ago, studiot said:

But added to these are numbers which are not prime yet still not divisible by any of the first 9 primes such as the example 2419 I gave.

All of these must also be checked.

I see what you mean. But I think we basically agree about that:

5 hours ago, joigus said:

Sorry, the problem reduces to how many numbers there are between 1 and 223'092'869 that are not divided by 1, 2, 3, 5, ..., 23.

So the decomposition of 223'092'870 into a pair of numbers x+y with x, y, not necessarily being prime, but being relative primes of 2, 3, 5, ..., 23, I think is the defining condition.

32 minutes ago, Tinacity said:

And I wanted to assume that the number of pairs which sum to N are given by the product: (3-2)*(5-2)*(7-2)*(11-2)*(13-2)*(17-2)*(19-2)*(23-2) and to have that confirmed if possible.

I'm way past my comfort zone here.

Fortunately @Sensei did it for all of us, and even though I'm not a great code reader, I think it's what the OP was asking.

 

 

 

[studiot]

2 hours ago, Tinacity said:

1)And I wanted to assume that the number of pairs which sum to N are given by the product: (3-2)*(5-2)*(7-2)*(11-2)*(13-2)*(17-2)*(19-2)*(23-2) and to have that confirmed if possible.

2) Then I wanted to assume that there were an equal number of pairs where the pair members are also divisible by 2. 

I don't see any justification for the first statement, (Which is think is wrong because of carries as below)

I don't understand the second statement at all.

44 minutes ago, Sensei said:

Yesterday, it was too late. OK. Now, I made program in C/C++:

The following beginning analysis may help,

Start with two nine digit numbers XXXXXXXXX  and YYYYYYYYY.
Allow all digits 0 through 9 including leading zeros, which will take care of the possibility of the actual numbers having less than 9 digits.

The last digit is a zero so  consider all possible pairs that can result in a zero.
Strike out those that have a factor from the disallowed list.

[math]\begin{array}{*{20}{c}}
   {Pair} \hfill & {Divisor} \hfill  \\
   {\left\{ {0,0} \right\}} \hfill & 2 \hfill  \\
   {\left\{ {1,9} \right\}} \hfill &  -  \hfill  \\
   {\left\{ {2,8} \right\}} \hfill & 2 \hfill  \\
   {\left\{ {3,7} \right\}} \hfill &  -  \hfill  \\
   {\left\{ {4,6} \right\}} \hfill & 2 \hfill  \\
   {\left\{ {5,5} \right\}} \hfill & 5 \hfill  \\
\end{array}[/math]

 

Hence the last digit (of each number) can be chosen in 2 possible ways  (as Tina says )

but

However since both add up to 10 there must be a carry to the next digit.

Also all possible last digits are now odd so from no on no number will be divisible by 2.

Since there is a carry, the two digits must add to 6 or 16

Listing these as before

[math]\begin{array}{*{20}{c}}
   {Pair} \hfill & {Divisor} \hfill  \\
   {\left\{ {0,6} \right\}} \hfill &  -  \hfill  \\
   {\left\{ {1,5} \right\}} \hfill &  -  \hfill  \\
   {\left\{ {2,4} \right\}} \hfill &  -  \hfill  \\
   {\left\{ {3,3} \right\}} \hfill &  -  \hfill  \\
   {\left\{ {8,8} \right\}} \hfill &  -  \hfill  \\
   {\left\{ {7,9} \right\}} \hfill &  -  \hfill  \\
\end{array}[/math]

Which yields 6 possible pairs, not 3 as Tina hopes

I will leave it to you to decide if any further divisors can be eliminated

Edited October 31, 2020 by studiot

[joigus]

I was a bit surprised that such a simple formula would hold for a problem like this. Prime numbers are quite unpredictable.

Prime gaps for example cannot be predicted by a general formula. So a formula giving all possible sum decompositions of products of primes...

I didn't see the flaw in the argument, because I didn't see the argument. But again, number theory is not within my comfort zone.

[Sensei]

43 minutes ago, studiot said:

The following beginning analysis may help,

What is wrong with the code?

It takes 7 seconds on my machine to execute this code in Tina's case.

59 minutes ago, studiot said:

The last digit is a zero so  consider all possible pairs that can result in a zero.

That is covered by the first line of the loop in check(), isn't?

Quote

if( ( a % 2 ) == 0 ) return( false );

Although, it could be handled better by simply skipping even numbers using:

	for( int i = 1; i < half; i += 2 ) {

Now it takes 5 seconds in Tina's case. But is less readable.

64 bit integers version:

#include <stdio.h>

//int primes[] = { 2, 3, 5, 7, 11, 13, 17, 19, 23, 29, -1 };
int primes[] = { 2, 3, 5, 7, 11, 13, 17, 19, 23, -1 };

// We're skipping prime 2, because of optimization in the main loop.
bool check(__int64 a, __int64 b) {
	for (int i = 1; primes[i] > 0; i++) {
		if ((a % primes[i]) == 0) return(false);
		if ((b % primes[i]) == 0) return(false);
	}
	return(true);
}

int main(int argc, int *argv[]) {
	__int64 count = 0;
	__int64 end = 1;
	printf("Primes: ");
	for (int i = 0; primes[i] > 0; i++) {
		printf("%d ", primes[i]);
		end *= primes[i];
	}
	printf("\n");
	printf("End %lld\n", end);
	__int64 half = end / 2;
	//for (__int64 i = 0; i < half; i++) { // Original.
	for (__int64 i = 1; i < half; i +=2 ) { // optimized to skip dividable by 2.
		__int64 a = i;
		__int64 b = end - a;
		if (check(a, b)) {
			//printf("Found %lld %lld\n", a, b);
			//printf("Found %lld %lld %lld\n", a, b, a+b );
			count++;
		}
	}
	printf("Count %lld\n", count);
	return(0);
}

 

Edited October 31, 2020 by Sensei