Jump to content

First Post on Primes


Tinacity

Recommended Posts

3 hours ago, Tinacity said:

Effectively deleted this post as I have to rethink a bit......Sorry for any confusion.

 

 

 

 

But your original post has been a success for you, as you now probably  know where you might go from here.  :) 

Edited by StringJunky
Link to comment
Share on other sites

23 hours ago, joigus said:

that are not divided by 1, 2, 3, 5, ..., 23 (the 1st 23 primes).

1 is not a prime and those are not the first 23 primes. Don't trust me with numbers. :doh:

 

8 hours ago, studiot said:

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

The first 9 primes, I should have said. Thank you @studiot.

Link to comment
Share on other sites

9 hours ago, Sensei said:

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:

Which looks good.

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

18 mln is over twice more than OP value.

Could you translate your program into BASIC, please, as that's the only programming language I understand?

Link to comment
Share on other sites

6 hours ago, Charles 3781 said:

Could you translate your program into BASIC, please, as that's the only programming language I understand?

If code takes 5-7 seconds on Core i7, in program written in C/C++, in BASIC it will take hours for the same job..

Learn C/C++ on https://en.cppreference.com/w/

Which line of code you don't understand? Tell me which line, I will tell you what it does (even though everything is pretty plain basic, and understandable without words)..

Maybe this?

if ((a % primes[i]) == 0)

% is modulo operator. https://www.google.com/search?q=modulo+operator+c

 

Quote

end *= primes[ i ];

It is equivalent to:

end = end * primes[ i ];

Edited by Sensei
Link to comment
Share on other sites

I have realised that I formulated my question incorrectly, let's say, by a factor of two, as it were.

And can only apologise humbly for wasting good folks time on here, attempting to advise me on the wrong question.

I am not used to attempting to describe my space of interest and I was so close to it, that I miss_described a basic aspect of my problem space.

Instead of asking folk to "consider 2*3*5*7*11*13*17*19*23 = 223092870 ( the product of the first 9 primes).. Call this number: N"

I should have doubled that.....Because it is the first 223092870 PAIRS of natural numbers summing to N I am interested in examining.....

Thus N in this case should be 4*3*5*7*11*13*17*19*23 = 446185740 so that I can form 223092870 pairs which sum to 446185740 from that.

And hoping therefore.......that I can then assume that the number of pairs (x,y) which sum to N, but where neither x or y  has any of the first 9 primes as an exact factor, is given by the product: (3-2)*(5-2)*(7-2)*(11-2)*(13-2)*(17-2)*(19-2)*(23-2) ?

And can also assume that the number of pairs (x,y) which sum to N, but where x and y are even but neither x or y has any of the first 8 odd primes as an exact factor, is also given by the product (3-2)*(5-2)*(7-2)*(11-2)*(13-2)*(17-2)*(19-2)*(23-2) ?

I think it better if I at least establish this first....before attempting any expansion of my questions from there.

 

I hope I haven't lost everyone with my amateurishness.....!!

 

 

 

 

 

Link to comment
Share on other sites

On 10/28/2020 at 8:26 AM, Tinacity said:

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

Haven't followed the thread but this seems a little ambiguous. Let's take a simpler example, N = 2 x 3 x 5 x 7 = 210. 

Now you want to consider the pairs of numbers that sum to 210, such as (1, 209), (2,208), ..., (209, 1). Do you care about order? Is (1,209) the same as (209,1) or different? Not a big issue, just a factor of 2, but nice to know what is the intended intepretation.

Now "... where neither is divisible by any of the primes which make its product?" was confusing to me. What is "its" in this context? Do you mean that since 209 = 11x19, and neither 11 nor 19 is one of 2, 3, 5, or 7, we count (1,209) and (209,1) as satisfying your condition? 

And you want to count the number of such pairs? Just want to make sure I'm understanding the question. Apologies to all if this has already been covered in the thread.

 

 

Edited by wtf
Link to comment
Share on other sites

More ambiguous than ever, since I just recently amended the question by a factor or 2, as it were.

But yes.....Your simpler example does encompass my intentions.

And (1,209) and (209,1) are two answers.

Yes.....the pairs with 209 = 11*19 are relative prime pairs (if we count 1 as a prime that is; and it wouldn't detract from the quality of answer I am hoping for anyway)

 I can see the confusion in the phrase "... where neither is divisible by any of the primes which make its product?"

Possibly because I didn't refer to each pair of numbers (x,y) which sum to N . Neither of those should be divisible by any of the factors of N.

 

 

 

 

 

@wtf

 

Here is my attempted amendment to my original question.

 

I have realised that I formulated my question incorrectly, let's say, by a factor of two, as it were.

And can only apologise humbly for wasting good folks time on here, attempting to advise me on the wrong question.

I am not used to attempting to describe my space of interest and I was so close to it, that I miss_described a basic aspect of my problem space.

Instead of asking folk to "consider 2*3*5*7*11*13*17*19*23 = 223092870 ( the product of the first 9 primes).. Call this number: N"

I should have doubled that.....Because it is the first 223092870 PAIRS of natural numbers summing to N I am interested in examining.....

Thus N in this case should be 4*3*5*7*11*13*17*19*23 = 446185740 so that I can form 223092870 pairs which sum to 446185740 from that.

And hoping therefore.......that I can then assume that the number of pairs (x,y) which sum to N, but where neither x or y  has any of the first 9 primes as an exact factor, is given by the product: (3-2)*(5-2)*(7-2)*(11-2)*(13-2)*(17-2)*(19-2)*(23-2) ?

And can also assume that the number of pairs (x,y) which sum to N, but where x and y are even but neither x or y has any of the first 8 odd primes as an exact factor, is also given by the product (3-2)*(5-2)*(7-2)*(11-2)*(13-2)*(17-2)*(19-2)*(23-2) ?

I think it better if I at least establish this first....before attempting any expansion of my questions from there

Link to comment
Share on other sites

1 hour ago, Tinacity said:

I should have doubled that.....Because it is the first 223092870 PAIRS of natural numbers summing to N I am interested in examining.....

Have you tried this out by hand for a simpler case, say N = 2 x 3 x 5 = 30? Then dropping the first and last gives you 3. Can you make your idea come out with that example? Is there something special about the case you're presenting?

Edited by wtf
Link to comment
Share on other sites

I have worked on smaller examples.....

It's any general result I am looking to establish.

I can see that for 2*3*5....If I multiply that by 2......The number of relative prime pairs, as it were......are indeed calculated from (3-2)*(5-2) = 3.

Similarly for 4*3*5*7.....Finding the number of prime or relatively prime pairs from (3-2)*(5-2)*(7-2) = 15

and 135 pairs for 4*3*5*7*11 .  Found by (3-2)*(5-2)*(7-2)*(11-2)

Is this the general case then.....? p1 to pn.....the number of prime/relatively prime pairs is found by (p1-2)*(p2-2)......(pn-2)

Or something around that....!!

I am generally aware that I am not being super exact in everything I am saying here......I hope that isn't too annoying for everyone.

 

 

 

 

Link to comment
Share on other sites

33 minutes ago, Tinacity said:

I can see that for 2*3*5....If I multiply that by 2......The number of relative prime pairs, as it were......are indeed calculated from (3-2)*(5-2) = 3.

Can you show your work in detail? I still don't understand the basic question. 

2*3*5 = 30. Multiply that by 2 and you get 60. Please explain the rest because I totally do not understand what we are doing here. Where did the -2's come from, that hasn't been part of your exposition.

ps -- Ok I totally don't get this. Pairs that sum to 60 and have no divisors among 2,, 3, 5: I get

1,59

11,49

13,47

17, 43

That's already four, eight if you distinguish order, and there are plenty more. So please explain clearly what you are doing.  Others are

19, 41

23, 37

29, 31

That's a total of 7, times 2 to account for order as you said earlier, so there are 14 pairs that satisfy your requirement, not 3.

 

33 minutes ago, Tinacity said:

Similarly for 4*3*5*7.....Finding the number of prime or relatively prime pairs from (3-2)*(5-2)*(7-2) = 15

Where do these -2's come from? In one example earlier you had 17-2 as a factor but that's not prime. Maybe it's just me but I do not understand what is being calculated. Can you work out a complete example, a simple one? Apologies if I'm being dense and this is obvious to everyone but me.

Those of you who wrote programs to solves this problem, what problem are you solving? Am I just missing something that's obvious to everyone else?

Edited by wtf
Link to comment
Share on other sites

If we look at the number 2*3*5 =30

We can form 15 natural number pairs (x,y) which can sum to 30

1+29, 2+28 , 3+27, 4+26, 5+25, 6+24, 7+23, 8+22, 9+21,10+20, 11+19, 12+18, 13+17, 14+16, and 15+15

If I double 30...to make 60

Then I double the number of pairs (x,y) (members of the natural numbers) which form this number.

I have 30 unique natural number pairs which sum to 60 (unique, as in order is also important...)

Question: How many of these pairs (x,y) are there, where neither x or y is divisible by the the primes of its product 4*3*5 ?

I want to assume that this can be calculated thus......(4-2)*(3-2)*(5-2) = 6

This could be from the following configuration of sums to 60

30/30 29/31 28/32 27/33 26/34 25/35 24/36 23/37 22/38 21/39 20/40 19/41 18/42 17/43 16/44 15/45 14/46 13/47 12/48 11/49 10/50 9/51 8/52 7/53 6/54 5/55 4/56 3/57 2/58 1/59

Here are the six:  29/31, 23/37, 19/41, 17/43, 13/47, and 7/53

Sorry if that factor of 2 error keeps creeping in and out of my narrative.....I am simply unused to actually describing my problem space.

 

Before moving to describe the focus of the issue I want to examine....I need this method of calculating....confirmed or not.

 

And it is pairs that I am referring to .......not primes or relative primes less than N.

 

But pairs which sum to N.

 

 

 

 

 

 

Edited by Tinacity
Link to comment
Share on other sites

29 minutes ago, Tinacity said:

I have 30 unique natural number pairs which sum to 60 (unique, as in order is also important...)

If order matters then you have 14 + 16 and 16 + 14 and likewise for all the other pairs except for 15 + 15, which is it's own reverse. Do you mean order doesn't count? Rather than saying it does?

29 minutes ago, Tinacity said:

29/31, 23/37, 19/41, 17/43, 13/47, and 7/53

What happened to 1/59?

I had a couple of mistakes in my own list, I had 11/49 which shouldn't be there, and I forgot 7/53. 

So there are 7 such pairs, 14 if order matters. I assume by your example that order DOESN'T matter. Still we have 7 pairs

1/59, 7/53, 13/47, 17/43, 19/41, 23/37, and 29/31. That's seven. I think we have them all.

The question comes down to taking 60 and asking, out of the first 30 positive integers, how many are divisible by at least one of 2, 3, or 5. Half are divisible by 2, 1/3 are divisible by 3 but we counted the ones divisible by 6 twice; and 1/5 are divisible by 5 but we counted the 10's and the 15's twice. But then we subtracted the ones divisible by 30 once too much so we have to add it back in. 

I believe you attack this kind of problem with the inclusion/exclusion formula. In fact the first example here shows how to count how many numbers from 1 to 100 are divisible by at least one of 2, 3, or 5, our exact problem here.

https://en.wikipedia.org/wiki/Inclusion–exclusion_principle

I jotted down some numbers but I was off-by-one somewhere, which doesn't surprise me.

 

 

 

Edited by wtf
Link to comment
Share on other sites

My apologies....I was thinking about a different aspect of my problem space when I talked about order there....Ignore the order reference, if you would. 6 pairs in n=60 is correct.

If we wish to call (1,59)...as one of those pairs....then, for 60 it is 7.....but this detail is irrelevant to any generalisation I seek for this matter.

I got 13/47 but not 11/49........hmmm.....

Oh yes.....I can see the potential reason for that issue arising.....It's because N itself, must not share any of the odd primes as a factor either.

I am getting into parts of the problem space I didn't want to reveal atm.......

I chose artificial examples....but chose them poorly.

The numbers (N) I have been working with....automatically share none of the prime factors less than the sqrt(N/2)

I think that the unexpected extra pairs you found, such as 11/49 are outcomes from N = 60 being divisible by all of the prime factors less than sqrt(N/2) where N=60

I will have to go and think about this forum approach......Thank you for your awesome input there.... @wtf

I know that what I just said may seem confusing and even inappropriate but this is a very personal project I have worked on for some considerable time...Please bare with me.

But you folks have certainly helped me see that I will have to think much harder about how I define my questions and answers.....

 

 

 

 

 

I might assume that I could ad the caveat "at least" to this general formula;   "p1 to pn.....the number of prime/relatively prime pairs is found by (p1-2)*(p2-2)......(pn-2)"

To cover for N which may share prime factors less than sqrt (n-2)

Link to comment
Share on other sites

1 hour ago, Tinacity said:

I chose artificial examples....but chose them poorly.

 

Is this a matter of being concerned that someone will steal your idea? If you post your actual problem perhaps someone can offer some help. 

For what it's worth, here's what I did with inclusion/exclusion. Suppose we want to know how many numbers from 1 through 30 are not divisible by any of 2, 3, or 5. We calculate how many ARE divisible by at least one of them as follows;

1/2 x 30 = 15

1/3 x 30 = 10

1/5 x 30 = 6

That adds up to 31.

Now for the double counts, which must be subtracted:

1/6 x 30 = 5

1/10 x 30 = 3

1/15 x 30 = 2

That adds up to 10, to be subtracted.

Now we must ADD back the triple counts: namely,

1/30 x 30 = 1.

So we have 31 - 10 + 1 = 22. Therefore there are 30 - 22 = 8 numbers NOT divisible by any of 2, 3, or 5. Indeed we can count them by hand: 1, 7, 11, 13, 17, 19, 23, and 29. Eight as calculated.

Now the problem is that we have not accounted for the pairs 29/31, or 23/37, etc., because the larger numbers of the pair are out of our range. So if you figure out how to account for the "sum to 60" aspect of the problem, you'll be able to work this out. 

Do feel free to give more information about your actual problem, or not, as you see fit. 

Then again when Hilbert offered to help Einstein with general relativity, Einstein at first welcomed his offer; but then realized that Hilbert was trying to solve the problem first and take credit. So maybe you're right not to give too much away! LOL.

 

ps -- Wait DUH! We forgot 11/49. I don't know why we both got confused about this. I solved the problem.

The trick is that if n is divisible by one of 2, 3, or 5, so is 60 - n. So the pairs (n, 60-n) where both elements are relatively prime to 2, 3, and 5 are exactly the same as the numbers n with the same property. So the solution is to do inclusion/exclusion on 30 to determine how many numbers are not divisible by 2, 3, or 5; and that's the number of pairs. In the case of 60 there are exactly 8 pairs:

1/59, 7/53, 11/49, 13/47, 17/43, 19/41, 23/37, and 29/31. That's eight. 

You can now write a program to do inclusion/exclusion on your original number N, or half of 2N if you think of it that way (that is, 2x3x5 = 30, multiply by 2 to get 60, then do inclusion/exclusion on 30). The "sum to 60" is a red herring, an aspect of the problem that adds confusion but doesn't change the problem. 

I believe that's it, but if I messed up I hope someone will jump in.

Edited by wtf
Link to comment
Share on other sites

@Tinacity,

ps -- Wait DUH! We forgot 11/49. I don't know why we both got confused about this. I solved the problem.

The trick is that if n is divisible by one of 2, 3, or 5, so is 60 - n. So the pairs (n, 60-n) where both elements are relatively prime to 2, 3, and 5 are exactly the same as the numbers n with the same property. So the solution is to do inclusion/exclusion on 30 to determine how many numbers are not divisible by 2, 3, or 5; and that's the number of pairs. In the case of 60 there are exactly 8 pairs:

1/59, 7/53, 11/49, 13/47, 17/43, 19/41, 23/37, and 29/31. That's eight. 

You can now write a program to do inclusion/exclusion on your original number N, or half of 2N if you think of it that way (that is, 2x3x5 = 30, multiply by 2 to get 60, then do inclusion/exclusion on 30). The "sum to 60" is a red herring, an aspect of the problem that adds confusion but doesn't change the problem. 

The number of pairs that sum to 60 where each element of the pair is not divisible by 2, 3, or 5, is exactly equal to the number of numbers between 1 and 30 not divisible by 2, 3, or 5. And this result generalizes under the conditions of your problem.

To do inclusion/exclusion on N = 2*3*5*7*11*13*17*19*23 you take:

- The sum of all 8-fold products of N (that is, every combination of 8 factors at a time);

- Minus the sum of all 7-fold products;

- Plus the sum of all 6-fold products;

etc. You then subtract the final sum from N, and that's the number of pairs where both elements are relatively prime. 

I believe that's it, but if I messed up I hope someone will jump in.

Edited by wtf
Link to comment
Share on other sites

20 hours ago, wtf said:

Where did the -2's come from, that hasn't been part of your exposition.

I don't know what the status of the question is, but this is exactly the part I didn't understand at all.

It seems like Tina is reconsidering and I on my part think everybody is being considerate and trying to understand the problem.

20 hours ago, wtf said:

Where do these -2's come from? In one example earlier you had 17-2 as a factor but that's not prime. Maybe it's just me but I do not understand what is being calculated. Can you work out a complete example, a simple one? Apologies if I'm being dense and this is obvious to everyone but me.

Those of you who wrote programs to solves this problem, what problem are you solving? Am I just missing something that's obvious to everyone else?

Not at all, @wtf. I think you understand it better than anybody else here. At least than me.

I applaud your suggestion to start with simpler numbers.

Link to comment
Share on other sites

1 hour ago, joigus said:

I applaud your suggestion to start with simpler numbers.

Not at all, @wtf. I think you understand it better than anybody else here. At least than me

I agree and indeed suggested such a thing in my first post in this thead.

I also agreethat wtf is best placed to analyse and Sensei to program answers.

The question has similar vagaries as the simpler one I posted

On 10/30/2020 at 9:06 PM, studiot said:

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.

Link to comment
Share on other sites

  • 2 weeks later...
On 11/2/2020 at 2:14 AM, wtf said:

Is this a matter of being concerned that someone will steal your idea? If you post your actual problem perhaps someone can offer some help. 

For what it's worth, here's what I did with inclusion/exclusion. Suppose we want to know how many numbers from 1 through 30 are not divisible by any of 2, 3, or 5. We calculate how many ARE divisible by at least one of them as follows;

1/2 x 30 = 15

1/3 x 30 = 10

1/5 x 30 = 6

That adds up to 31.

Now for the double counts, which must be subtracted:

1/6 x 30 = 5

1/10 x 30 = 3

1/15 x 30 = 2

That adds up to 10, to be subtracted.

Now we must ADD back the triple counts: namely,

1/30 x 30 = 1.

So we have 31 - 10 + 1 = 22. Therefore there are 30 - 22 = 8 numbers NOT divisible by any of 2, 3, or 5. Indeed we can count them by hand: 1, 7, 11, 13, 17, 19, 23, and 29. Eight as calculated.

Now the problem is that we have not accounted for the pairs 29/31, or 23/37, etc., because the larger numbers of the pair are out of our range. So if you figure out how to account for the "sum to 60" aspect of the problem, you'll be able to work this out. 

Do feel free to give more information about your actual problem, or not, as you see fit. 

Then again when Hilbert offered to help Einstein with general relativity, Einstein at first welcomed his offer; but then realized that Hilbert was trying to solve the problem first and take credit. So maybe you're right not to give too much away! LOL.

 

ps -- Wait DUH! We forgot 11/49. I don't know why we both got confused about this. I solved the problem.

The trick is that if n is divisible by one of 2, 3, or 5, so is 60 - n. So the pairs (n, 60-n) where both elements are relatively prime to 2, 3, and 5 are exactly the same as the numbers n with the same property. So the solution is to do inclusion/exclusion on 30 to determine how many numbers are not divisible by 2, 3, or 5; and that's the number of pairs. In the case of 60 there are exactly 8 pairs:

1/59, 7/53, 11/49, 13/47, 17/43, 19/41, 23/37, and 29/31. That's eight. 

You can now write a program to do inclusion/exclusion on your original number N, or half of 2N if you think of it that way (that is, 2x3x5 = 30, multiply by 2 to get 60, then do inclusion/exclusion on 30). The "sum to 60" is a red herring, an aspect of the problem that adds confusion but doesn't change the problem. 

I believe that's it, but if I messed up I hope someone will jump in.

I think that we just use Eulers Totient to calculate this kind of thing.

Phi(30) = (3-1)(5-1) = 8

If we are looking at the thirty pairs for n = 60 then it is phi(60) divided by 2....... or 8 pairs.

But what if we consider the first 210 sum pairs (x,y) of a number n? Where n is greater than 420. And n does not share an odd factor with 210

e.g     n = 454

How many relatively prime pairs should we find?

You see....this is much closer to my problem space.......I have been trying to focus on the "most difficult" numbers for so long, that I had become unfamiliar with the problem space we were first discussing.....where n was a product of primes......

I am so unused to describing any aspect of my problem space that I made big mistakes in presenting it the way I did.....I can see that now and can only apologise for that....and vow to try harder to avoid that issue.

 

Edited by Tinacity
Link to comment
Share on other sites

Relative to 210 (the number of pairs being considered)

 

I would say that this is calculated using Euler's Totient.

I am using the less formal expression of the Totient formula.

I am NOT using (1-1/2)(1-1/3) etc........but the more accessible.... (3-1)(5-1)(7-1) version.

So....for 210 pairs (x,y) of n= 454, where x and y are natural numbers.......We use Euler's Totient to calculate the number of relative prime pairs (relative to the number of pairs) thus (3-2)(5-2)(7-2) = 15........."-2" being used, instead of "-1" in Euler's Totient, because each of the factors [3,5 and 7] knock out two pairs instead of only one. They would "knock out" only 1 pair at a time, when n shares any of those factors.

Edited by Tinacity
Link to comment
Share on other sites

Does the silence mean I goofed up on my whole narrative too many times?

Or discomfort with the implication that I am withholding my main project? That isn't a matter of disrespect......Just protecting a LOT of work.

Or do community members feel that my fifteen minutes of attention are up?

Or is it that I simply make no sense, still?

Or that my presentation style is just too casual, prosaic and/or inaccurate.

Or is it boredom.....lol !!?

Link to comment
Share on other sites

Create an account or sign in to comment

You need to be a member in order to leave a comment

Create an account

Sign up for a new account in our community. It's easy!

Register a new account

Sign in

Already have an account? Sign in here.

Sign In Now
×
×
  • Create New...

Important Information

We have placed cookies on your device to help make this website better. You can adjust your cookie settings, otherwise we'll assume you're okay to continue.