/sci/ - Science & Math

[Anonymous No.6458583]

Checked the catalog for a programming thread but didn't see one. Posting here on /sci/ because I don't think any other board can answer my question. I took an into to computer science course at my local community college, not because I want that as my career, only because I think it's interesting. Anyway, on to the question. I think I saw someone on here post something like "Is there any way to find 3 consecutive integers each being a multiple of 3 5 and 7 respectively without just using brute mathematical force?", so I thought that would be a good beginner program to write. My question is if this is the most efficient way to
A) answer the question
B) code this program
I wrote the program to be variable, in that you can set the multiples to whatever you choose, and set an upper limit that the consecutive set cannot exceed. I understand that going through all of the nested iterations is a huge resource strain (I think?).
>pic related is the program and execution which took about a minute

[Anonymous No.6458646]

3x + 1 = 5y
5y + 1 = 7z
3x + 2 = 7z

y = (3x + 1)/5 = (21x + 7)/35
z = (3x + 2)/7 = (15x + 10)/35

y - z = (6x - 3)/35

35z - 35y + 6x = 3

35(z - y) = 3 - 6x

for x > 1, LHS is negative. Hence y > z contrary to the hypothesised ranking of the values.

[Anonymous No.6458747]



for (var i=1; i<1000;i++)
{
if (!(i%3) && !(i%5) && !(i%7))
alert(i + " is a multiple of 3,5,and 7");
}


took me 3 seconds
I hope I understood the problem
http://jsfiddle.net/Qjmg2/

[Anonymous No.6458748]

3x + 1 = 5y
5y + 1 = 7z
3x + 2 = 7z

y = (3x + 1)/5 = (21x + 7)/35
z = (3x + 2)/7 = (15x + 10)/35

y - z = (6x - 3)/35

35(y - z) = 6x - 3 = 10y - 5 = 14z - 7

3(2x - 1) = 5(2y - 1) = 7(2z - 1) = n [A]

all I got

[Anonymous No.6458751]

>>6458747
sorry for bad formatting, wrote on muh nexus

[Anonymous No.6458758]

>>6458747
>>6458751
The original question was a little more involved than that. It asked what the smallest set of consecutive integers was given three multiples. Like in my pic, given the three multiples 13,19, and 37, the lowest set of consec integers was 9100, 9101, and 9102. I know my program works, I was just wondering like, if there was a more efficient way of using my computers resources to find the same result. Thank you for your input though

[Anonymous No.6458772]

I can at least think of a faster way to calculate this. Use a sieve for multiples of 3,5,7 and search for three consecutive bits.

[Anonymous No.6458797]

>>6458772
Scratch this. Has to be consecutive.

For starters, you don't need to do 7142 iterations of c if your 3-5 don't match up.

>for(a=0; a<=max; a+=aMul)
>>for(b=0; b<=max; b+=bMul)
>>>if(b-a==1)
>>>for(c=0; c<=max; c+=cMul)
>>>>if(c-b==1)
>>>>>cout<<endl<<a<<" "<<b<<" "<<c;

No need for braces by the way. These are all one-command iterators.

[Anonymous No.6458806]

>>6458797
Yes I knew there was a more efficient way! Thank you, it is so simple. And thank you for the tip as well. What is sieve?

[Anonymous No.6458809]

>>6458797

This is not necessary anyway.

The solution set will have a first element given by n * (A * B * C) - (C+2), where n is a natural number.

[Anon !!3wHWqEMsmPf No.6458812]

>>6458583
>>>/g/
Also, you might be looking for projecteuler.net if you're into algorithmic programming problems like this.

[Anonymous No.6458815]

>>6458806
http://en.wikipedia.org/wiki/Sieve_of_Eratosthenes
This is a good example.

I provided a solution above. The code to print out all of the series up to a maximum value would be:

for( i = 0; i < max; i+=(a*b*c)) cout << i - (c+2) << " " << i - (c+1) << " " << i - c << endl;

[Anonymous No.6458819]

>>6458758
I'm gonna check your pic

So, If I understand you, you want three CONSECUTIVE numbers, and ALL of them of have to multiples of 3, 5 and 7, correct?

like: http://jsfiddle.net/M9Hr4/2/ ?

[Anonymous No.6458823]

>>6458819
my bad, you can do this, you just want a more efficient way, right?

[Anonymous No.6458826]

I think this solves your problem.

http://en.wikipedia.org/wiki/Chinese_remainder_theorem

[Anonymous No.6458827]

>>6458826
You're basically trying to solve
x = 0 (mod a)
x + 1 = 0 (mod b)
x + 2 = 0 (mod c)

[Anonymous No.6458833]

>>6458823
You can not do this.
if x is a multiple of n (n integer > 1) then x + 1 is not a multiple of n. Because if it were, then
x = nu, x + 1 = nv
x + 1 - x = nv - nu = n(u - v) = 1

and this is an epic contradiction because n and u and v are all integers and n > 1

[Anonymous No.6458835]

>>6458833
yea, my program is far from efficient since I go through every single numb

[Anonymous No.6458843]

>>6458835

Yeah but this solution is far superior to OPs
>>6458747
OP used 3 for loops, which is O(N^3), something insanely undesirable

[Anonymous No.6458847]

this solution is far superior to OPs
>>6458747


OP used 3 for loops, which is O(N^3), something insanely undesirable

[Anonymous No.6458848]

>>6458819

this solution is far superior to OPs

OP used 3 for loops, which is O(N^3), something insanely undesirable

There I think I finally clicked the right one (deleted many posts)

[Anonymous No.6458860]

>>6458833
>>6458819
>>6458835

You both misunderstood each other. OP, he gave an obvious proof that it's impossible to have three consecutive numbers m, n, p such that each of them are multiples of 3, 5,and 7.

However, I know that's not what you're asking for. You're asking for m to be a multiple of 3, n to be a multiple of 5, and p to be a multiple of 7 then that's entirely different. I can tell because of this post.
>>6458758


>>6458748
I'm really tired and really busy so I can't help now but try applying a homomorphism to some modulo ring. You might be able to find a general solution.

[Anonymous No.6458865]

>>6458860
>You might be able to find a general solution.

I already posted a fucking general solution in this thread.

>>6458815
>>6458809
This is it. It works for any 3 numbers provided they are not equal and c > b > a. They can be even, share roots, etc.

[Anonymous No.6458869]

>>6458865
An algorithm is not a general solution. By general solution I mean a single equation that produces a set of integer solutions.

[Anon !!3wHWqEMsmPf No.6458874]

>>6458835
As a first crack at it, I'd try going through the multiples of the highest number and checking the two numbers underneath.

For instance, if you give it 13, 17, and 19, you would count by 19s. For iterating variable a, if and only if (19a - 1) is divisible by 17, then you can go on to check if (19a - 2) is divisible by 13. That way, you can skip all those extra 13s altogether. 19a is your high number, really the only one you'd be doing any operations on, and (19a - 1) along with (19a - 2) would be your other outputs if they pass the checks.

A simple check for divisibility will involve using the % operator. I can write out the program here if you want me to, but I warn you, it'll be in Java.

[Anonymous No.6458878]

>>6458869
It's not an algorithm, fuckwit. The set of integer solutions is (A*B*C)*n-(C+2) for n = 1,2,3,4..., A =/= B =/= C and C > B > A.

[Anonymous No.6458900]

>>6458878
For the multiples to be three consecutive numbers, either B, both A & C, or all three must be odd.

Make the program throw a fit if if doesn't meet those conditions.

[Anonymous No.6458921]

>>6458833
Fuck, I finally understood after looking at OP's pic.

and reading:

>>6458860
>You're asking for m to be a multiple of 3, n to be a multiple of 5, and p to be a multiple of 7

I did this:
>http://jsfiddle.net/M9Hr4/4/

I will compare my current method to
>>6458815
>>6458809

[Anonymous No.6458923]

>>6458833
Fuck, I finally understood after looking at OP's pic.

and reading:

>>6458860
>You're asking for m to be a multiple of 3, n to be a multiple of 5, and p to be a multiple of 7

I did this:
>http://jsfiddle.net/M9Hr4/4/

I will compare my current method to
>>6458815
>>6458809

[Anonymous No.6459314]

I have the solution. If you're still around OP tell me and I'll type it up.

[Anonymous No.6459959]

>>6459314
I am still here, my question was basically answered already, many anons have posted much more efficient codes than mine. I'd still like to see yours though

[Anonymous No.6459990]

>>6458758

Your program is terribly inefficient. You have three nested loops which check a ton of combinations that are invalid from the outset, like 13,19,37 and then 13,19,74, and 13,19 101 etc.

The best way to do it would be something like:

for(int i = 0; i < max; i++){
if(i % num1 == 0 && (i+1) % num2 == 0 && (i+2) % num3 == 0)
cout<<i<<endl;
}

Also, your main function lacks a return statement

[Anonymous No.6460000]

>>6458826
>>6458827

Nice.

http://www.wolframalpha.com/input/?i=9100+mod+105%2C+9101+mod+105%2C+9102+mod+105

This is the approach I'd take, OP.

[Anonymous No.6460013]

One of my assignments at uni is to program a "maze" using only arrays, conditionals, while loops, and functions, and fill it with "rats".

The maze has 4 rooms (it's a shit maze) and each room has probabilities that the rats will leave it for some of the other rooms each "round". Some paths are one-way, others have no connecting paths.

I saw in the criteria sheet that they say it's okay to have fractions of rats because it's a probability thing. Which I assume is a green light to just multiply room population by probability of leaving (ex 14 * 0.24) which is retarded in my view.

What I'm doing is making an array, which is essentially a 100 sided die, for each room and if the probability of moving to room 2 is 0.24 then it marks 24 of the sides with the number 2, and so on. I've done this already and it works fine.

Next I'm going to have it roll for chance for each rat in that room, and then move those rats (as in minus them from the population integer for the room) to a "holding room" so that they don't interfere with the die roll of the room they're going to go to.

Then when all 4 rooms have had their dice rolls and their rats put into the holding rooms, I'm going to just transfer all the holding rooms into the actual rooms, and that'll be the end of the round.

Doing it this way actually makes the rat movements probabilistic as opposed to just population * probability, go.

That probably made no sense.

[Anonymous No.6460016]

>>6460013
Oh, the whole point is to plot where the rats end up after 30 rounds and talk about probability and whatnot.

[Anonymous No.6460036]

>>6460013

I'm gonna try and have a crack at this.

What you want to do is have two instances of the maze, one where the rats are before you move them, and another where they will be. What you want to have is an array like:

double movechance[numrooms][numrooms]

which contains the probability of a rat moving from one room into another. Next you have:

double ratsinroom[numrooms]

which will contain the amount of rats currently in each room. You must then allocate a new array

double ratstorooms[numrooms]

which you must initialize to zero. Then:

for(i = 0; i < numrooms; i++){
for(j = 0; j < numrooms; j++){
ratstorooms[j] += movechance[i][j] * ratsinrooms[i];
}
}

after this you delete ratsinrooms[]; and you set ratsinrooms to point towards the new situation:

ratsinrooms = ratstorooms;

this sets you up for the next pass

[Anonymous No.6460045]

>>6460036
Interdasting.

[Anonymous No.6460046]

>>6460036

I forgot to add: if you haven't had new, delete, pointers etc. yet, just make a double ratsinroom[numrooms] and double ratstorooms[numrooms], and then copy ratstorooms into ratsinrooms and set ratstorooms back to all zeros to set yourself up for the next pass

[Anonymous No.6460051]

>>6460013
>One of my assignments at uni is to program a "maze" using only arrays, conditionals, while loops, and functions, and fill it with "rats".

>program a game using only the elemental, most commonly used program constructs
>only

[Anonymous No.6460067]

>>6459959
Ok, I don't know how to edit equations on this board so you're gonna have to deal with the ugly pleb formatting:


We have a sequence 3x, 5y, 7z such that
A: 3x + 1 = 5y
B: 5y + 1 = 7z

C: 5y % 2 = 0 [confirm this by considering 3x + 1 % 2]

5 % 2 = 1, therefore if C holds then y%2 = 0

Hence 5y = 5*2*y' = 10y'

7z = 10y' + 1 = 3x + 2

7(10n + 3) = 10y' + 1 = 3x + 2 [Confirm this by considering under which circumstances the least significant digit of any multiple of 7 is 1]

70n + 21 = 3x + 2
70n + 19 = 3x
70n + 10 + 9 = 3x
70n + 10 = 3k [this is a necessary precondition for the above line such that 3k + 9 = 3x]

10(7n + 1) = 3k
(7n + 1) % 3 = 0 [since 10%3 = 1]

Observe that the lowest integer n for which the above line holds is 2.

7(2 + n') + 1 = 14 + 7n' + 1 = 15 +7n'

7 % 3 = 1 hence n' % 3 = 0.

Hence all solutions are given by setting n' to some multiple of 3 (including 0*3 = 0) and substituting the result back.

Example:

So for n' = 3, we have
n = 2 + n' = 5

70n + 19 = 350 + 19 = 369 = 3x
5y = 370
7z = 371

Or let n' = 6

n = 8

3x = 70(n) + 19 = 579
5y = 580
7z = 581

You can confirm that the above example holds using google for a calculator or whatever.

There you have it, and non-general specific solution for the case of ax, by, cz with a = 3, b = 5, c = z

[Anonymous No.6460073]

>>6460067
last line should say c = 7

[Anonymous No.6460080]

>>6460067
Python program to output the results:


for i in range(10):
n = 3*i + 2
three_x = 70*n + 19
five_y = three_x + 1
seven_z = five_y + 1
print(three_x, five_y, seven_z)



[Anonymous No.6460084]

>>6460080
bleh, indent everything under "for i in range(10)" or it won't run

[Anonymous No.6460088]

>>6460080
One final thing before I quit spamming the thread; this program runs in linear time proportional to the argument of range.

[Anonymous No.6460106]

f[a,b,c,max] returns a list of positive integers x less than or equal to max such that the set {x, x+1, x+2} has one element divisible by a, a second distinct element divisible by b, and a third divisible by c

[Anonymous No.6460113]

>>6460106
This is probably the most computationally expensive solution ITT.

[Anonymous No.6460130]

Okay so I think OP left but there's an interesting quirk to the original question.

Once you've found the FIRST set of numbers that satisfies your requirements, just keep adding the Lowest Common Denominator of [a,b,c] to the members of the first set to find all the other sets.

Like in OP's program all the sets are 13*19*37 apart because 13, 19 and 37 are coprime so their LCD is just their product.

[Anonymous No.6460144]

>>6460130

Wait hang on that's only true when the second-lowest number in [a,b,c] is larger than half the largest one, my bad.

I think.

Okay look what I can definitely tell you for realsies is that once you have all the solutions below a*b*c (or a*b*c*d*e or whatever) you just keep adding a*b*c to all of them to find all the remaining solutions.

[Anonymous No.6460240]

>>6460113
yeah it's not great. Luckily this is much better. Little did I know that Mathematica has a Chinese Remainder Theorem calculator built into it. That part is instantaneous - the time-consuming part is adding on the LCM of the integers as many times as necessary.

[Anonymous No.6460286]

>>6460240
It is still more complex that just calculating 70(3 + 2i) + 19 and adding 1 and 2 to it for the consecutives.

[Anonymous No.6460295]

>>6460286
That being said your solution is, too be fair, a general one.