number finding
Pages: 12
I tried to find the solution for this problem :
a+b+c+d+e+f+g+h+i+j+k....=1286
(a*b*c*d*e*g*h*i*j*k....) mod 65537 = 16628
the same numbers used to find 1286 should be used to find 16628
numbers used can be from 97 to 122
when I added
97+101+102+105+106+107+108+109+110+112+114+115=1286
but
(97*101*102*105*106*107*108*109*110*112*114*115) mod 65537 = 6825
2262746359185661109376000 mod 65537 = 6825 which is wrong because it is not 16628
2262746359185661109385803 mod 65537 = 16628 but I could not find what are the numbers that
when added give 1286 and when multiplied together mod 65537 give 16628
Moreover there are many possibilities to get 1286 and many possibilities to get 16628 but I cannot
find the possibility that give 1286 and 16628 so any help would be appreciated on how to find this possibility.
a+b+c+d+e+f+g+h+i+j+k....=1286
(a*b*c*d*e*g*h*i*j*k....) mod 65537 = 16628
the same numbers used to find 1286 should be used to find 16628
numbers used can be from 97 to 122
when I added
97+101+102+105+106+107+108+109+110+112+114+115=1286
but
(97*101*102*105*106*107*108*109*110*112*114*115) mod 65537 = 6825
2262746359185661109376000 mod 65537 = 6825 which is wrong because it is not 16628
2262746359185661109385803 mod 65537 = 16628 but I could not find what are the numbers that
when added give 1286 and when multiplied together mod 65537 give 16628
Moreover there are many possibilities to get 1286 and many possibilities to get 16628 but I cannot
find the possibility that give 1286 and 16628 so any help would be appreciated on how to find this possibility.
If you're here you probably know how to program and how to compile. Write a brute-force program that do it :)
this is a very interesting and realistic answer :)
the problem is that I am not good at programming . Could you help me by
telling me how to do it ?
the problem is that I am not good at programming . Could you help me by
telling me how to do it ?
how can I write a brute force program that add numbers (between 97 and 122)
and every time it finds 1286 , it takes it addends multiply them together then calculate the result mod 65537 to see if the result is 16628 and if it is then output both equations with their results ( 1286 and 16628) and their addends and factors??
and every time it finds 1286 , it takes it addends multiply them together then calculate the result mod 65537 to see if the result is 16628 and if it is then output both equations with their results ( 1286 and 16628) and their addends and factors??
Last edited on
closed account (EwCjE3v7)
Well for a start you would want a type that can hold a*b*c*d*e*g*h*i*j*k.
Next you will need to start all your numbers at 97, and go through every equation until you find the correct one.
I would recommend using a vector or array for holding your numbers. Iterate through your numbers and increment one each time and do your equation again until you get it.
Go through this http://apcentral.collegeboard.com/apc/public/repository/ap01.pdf.lr_7928.pdf for big numbers. Really useful if you are going to be working with big numbers a lot.
Take a look at this, which I got from stackoverflow: https://mattmccutchen.net/bigint/
Next you will need to start all your numbers at 97, and go through every equation until you find the correct one.
I would recommend using a vector or array for holding your numbers. Iterate through your numbers and increment one each time and do your equation again until you get it.
Go through this http://apcentral.collegeboard.com/apc/public/repository/ap01.pdf.lr_7928.pdf for big numbers. Really useful if you are going to be working with big numbers a lot.
Take a look at this, which I got from stackoverflow: https://mattmccutchen.net/bigint/
Last edited on
I recommend applying the formula ne555 mentioned for integer multiplication under modulus.
Personally I would use a backtracking algorithm to search through all the possibilities, while storing partial sums and products along the way. Regardless of what algorithm you choose to implement, checking for a sum of 1286 before calculating the product will help with speed tremendously.
Personally I would use a backtracking algorithm to search through all the possibilities, while storing partial sums and products along the way. Regardless of what algorithm you choose to implement, checking for a sum of 1286 before calculating the product will help with speed tremendously.
| (a*b) mod m = [ (a mod m)*(b mod m) ] mod m |
Prove it :P
(no I'm not doubting it, I just want to see what the proof looks like)
I think this is what you want:
http://math.stackexchange.com/questions/178424/modulus-distributing-over-multiplication
http://math.stackexchange.com/questions/178424/modulus-distributing-over-multiplication
This problem seems surprisingly fun to me. Got no clue how to solve it, but wrote a program to find the minimal number X for which the system
a+b+c+d+e+f+g+h+i+j+k....=X
(a*b*c*d*e*g*h*i*j*k....) mod 65537 = 16628
has a solution where all inputs are between 97 and 122.
I am now waiting for the program to terminate (it is kind of slow because I decided to use my large integer library to avoid any possible overflow issues).
Of course, finding this minimal number X doesn't help to solve the original problem (unless X turns out to be more than 1286, in which case the original problem has no solution).
a+b+c+d+e+f+g+h+i+j+k....=X
(a*b*c*d*e*g*h*i*j*k....) mod 65537 = 16628
has a solution where all inputs are between 97 and 122.
I am now waiting for the program to terminate (it is kind of slow because I decided to use my large integer library to avoid any possible overflow issues).
Of course, finding this minimal number X doesn't help to solve the original problem (unless X turns out to be more than 1286, in which case the original problem has no solution).
Last edited on
What can I say : As I am very weak newbie in programming , in the present moment , I cannot write a program . So many thanks Tition that you did it in my place .
X is 1286 FOR SURE
a+b+c+d.......=1286
(a*b*c*d*e*g*h*i*j*k....) mod 65537 = 16628
it is not difficult . The only issue that it needs a program that is able to do it quickly : if I do it by hand and there are 5000000 possibilities I will stay 50 years to solve
X is 1286 FOR SURE
a+b+c+d.......=1286
(a*b*c*d*e*g*h*i*j*k....) mod 65537 = 16628
it is not difficult . The only issue that it needs a program that is able to do it quickly : if I do it by hand and there are 5000000 possibilities I will stay 50 years to solve
The smallest sum for which one can get the prescribed product is:
a+b+c+d+.......= 539 (<-the smallest value for which the problem has a solution)
(a*b*c*d*....) mod 65537 = 16628
I have some idea how to find a solution to the original problem... having a function to enumerate all partitions of a number seems quite useful, maybe I should spend some time writing one (I have some very old implementation which uses way too much RAM).
a+b+c+d+.......= 539 (<-the smallest value for which the problem has a solution)
(a*b*c*d*....) mod 65537 = 16628
I have some idea how to find a solution to the original problem... having a function to enumerate all partitions of a number seems quite useful, maybe I should spend some time writing one (I have some very old implementation which uses way too much RAM).
I must admit that after that many years of hacking it I still did not have a function to generate all possible vector partitions of a given vector. Now that this is fixed, the OP's problem is actually quite easy:
111 *113^{4}* 117 *120* 121^{2}* 122^{2}=55372516661988719724960 = 16628 mod 65537
111+113*4+117+120+121*2+122*2 = 1286
111 *113^{4}* 117 *120* 121^{2}* 122^{2}=55372516661988719724960 = 16628 mod 65537
111+113*4+117+120+121*2+122*2 = 1286
And you just did a project Euler or some other challenge for him without providing hints on things to try :p I was thinking he could do dynamic programming for the sums and them once you find those brute force and it wouldn't take anywhere near as long as brute forcing the whole thing
Yep, the reason I did not post any hint as to how I did it is because we were given no context (I don't want to be doing someone's job interview homework question).
Other than that, what I did was:
1. Start generating all partitions of 1286 using elements of the set {97, ... 122}. Notice that my answer used only large numbers - that was because I was generating partitions in reverse lexicographic order.
Most of the technical difficulty lies in generating those partitions.
2. I multiplied the elements of the partition and computed mod 65537 until I got 1286.
How did I know the whole thing will work out so fast - it took about 4 seconds? (Before you say anything, yes, I could program it to work a tenth of a second but did not bother to optimize or use any of the problem's specifics).
Well the math behind it is this. Multiplication by an non-zero (mod 65537) number (mod 65537) is a one-to-one map. That means that multiplying every number by 97, for example, yields a ``good and uniform'' shuffling of the numbers between 1 and 65536. That means that if you pick, say, a hundred random integers between 1 and 65536, and multiply them, your chance of hitting 16628 by pure luck is approximately 1 in 65537.
That means that, if you start generating partitions of 1286 using your set of allowed values (partition = way to represent 1286 as a sum of numbers in the set), then if you are regularly lucky, you expect to get a solution after only 65537 tries. Checking that a partition of 1286 gives a solution is awfully fast - say 10 multiplications mod 65537, (each multiplication is 1 machine instruction and so is each mod operation). So checking a partition is practically instantaneous.
So the whole bottleneck is: generate as many different partitions of 1286 as you can as fast as you can.
Other than that, what I did was:
1. Start generating all partitions of 1286 using elements of the set {97, ... 122}. Notice that my answer used only large numbers - that was because I was generating partitions in reverse lexicographic order.
Most of the technical difficulty lies in generating those partitions.
2. I multiplied the elements of the partition and computed mod 65537 until I got 1286.
How did I know the whole thing will work out so fast - it took about 4 seconds? (Before you say anything, yes, I could program it to work a tenth of a second but did not bother to optimize or use any of the problem's specifics).
Well the math behind it is this. Multiplication by an non-zero (mod 65537) number (mod 65537) is a one-to-one map. That means that multiplying every number by 97, for example, yields a ``good and uniform'' shuffling of the numbers between 1 and 65536. That means that if you pick, say, a hundred random integers between 1 and 65536, and multiply them, your chance of hitting 16628 by pure luck is approximately 1 in 65537.
That means that, if you start generating partitions of 1286 using your set of allowed values (partition = way to represent 1286 as a sum of numbers in the set), then if you are regularly lucky, you expect to get a solution after only 65537 tries. Checking that a partition of 1286 gives a solution is awfully fast - say 10 multiplications mod 65537, (each multiplication is 1 machine instruction and so is each mod operation). So checking a partition is practically instantaneous.
So the whole bottleneck is: generate as many different partitions of 1286 as you can as fast as you can.
Last edited on
Thank you very much Tition , I really appreciate your help and efforts and admire them.
"(I don't want to be doing someone's job interview homework question)"
The part of finding both numbers represents only 25 % of a big challenge . The real challenge begins now that is the 75 % . However as I already understood the 75 % , this 25% was the problem for me because even if I understood how to solve the 75% I cannot solve the 100% as the 75% is related to the 25% which if not solved the whole challenge cannot be solved . So you did not do my challenge let alone for "job interview homework question". Finding both numbers is not difficult at all , the problem is it cannot be done by hand and I cannot write a brute force program that can do it for me . I never learned computer programming , I never studied it at university or school or any institution , No one , absolutely no one taught me about programming or even computer stuff and I had and I have no one to help me or show me when I am stuck ; I always counted on myself to solve these problems but I understood by time that when you practise something new alone by yourself , you come to a level that you could not surpass if you do not get some push or help from others . No one can progress alone without some support . Moreover , I begin to know about normal computer since three years ago let alone for being able to write a program which require many years of training and studying . So it is normal that I cannot write a program
Anyway Thank you again Tition it was a great gesture from you that I really appreciate
"(I don't want to be doing someone's job interview homework question)"
The part of finding both numbers represents only 25 % of a big challenge . The real challenge begins now that is the 75 % . However as I already understood the 75 % , this 25% was the problem for me because even if I understood how to solve the 75% I cannot solve the 100% as the 75% is related to the 25% which if not solved the whole challenge cannot be solved . So you did not do my challenge let alone for "job interview homework question". Finding both numbers is not difficult at all , the problem is it cannot be done by hand and I cannot write a brute force program that can do it for me . I never learned computer programming , I never studied it at university or school or any institution , No one , absolutely no one taught me about programming or even computer stuff and I had and I have no one to help me or show me when I am stuck ; I always counted on myself to solve these problems but I understood by time that when you practise something new alone by yourself , you come to a level that you could not surpass if you do not get some push or help from others . No one can progress alone without some support . Moreover , I begin to know about normal computer since three years ago let alone for being able to write a program which require many years of training and studying . So it is normal that I cannot write a program
Anyway Thank you again Tition it was a great gesture from you that I really appreciate
this is really an interesting concept " dynamic programming" I will try to learn more about it thanks
I couldn't help but notice that the numbers 97-122 are the ascii codes of the lowercase letters from a to z. Does that have anything to do with the context of the problem?
wonderful that you notice it . It has to do with ASCII values . Can you tell me how many possibilities between 97-122 that can give
a+b+c+d+...=1286
(a*b*c*d.....) mod 65537 = 16628
or there is only one this possibility :
111 *113^{4}* 117 *120* 121^{2}* 122^{2}=55372516661988719724960 = 16628 mod 65537
111+113*4+117+120+121*2+122*2 = 1286
??
a+b+c+d+...=1286
(a*b*c*d.....) mod 65537 = 16628
or there is only one this possibility :
111 *113^{4}* 117 *120* 121^{2}* 122^{2}=55372516661988719724960 = 16628 mod 65537
111+113*4+117+120+121*2+122*2 = 1286
??
Last edited on
I am pretty sure the number of solutions is astronomical. From the back-of-napkin math considerations I posted, you expect to get approximately
(# of partitions of 1286)/65536 solutions.
Now I am fairly certain the number of partitions of 1286 is very large (I haven't done the math (not quite sure how to do it even) but it should be at least in the whereabouts of 25^10, so that will be well in the trillions. So, again from a back-of-napkin consideration, you expect at least hundreds of thousands millions of solutions, but probably I am wrong by orders of magnitude.
(# of partitions of 1286)/65536 solutions.
Now I am fairly certain the number of partitions of 1286 is very large (I haven't done the math (not quite sure how to do it even) but it should be at least in the whereabouts of 25^10, so that will be well in the trillions. So, again from a back-of-napkin consideration, you expect at least
Last edited on
Pages: 12