Open Side Menu Go to the Top
Register
wall street quant interview question wall street quant interview question

04-08-2014 , 02:39 PM
Quote:
Originally Posted by masque de Z
Well i already gave a suggestion like 2+3*5*7*11*13=15017. That number is already not a multiple of 2,3,5,7,11,13. You could continue doing things like 3*7*11*13*17+2 etc and at least those would be forced to be if composite multiples of 19 or 23 or ...223 etc Then i considered 2^(2^n)+1 numbers. I am just trying to see if there is some construction that has multiple advantages that make it harder to be composite.
Not particularly enamoured with either the problem or the proposed solution, tbh. Effectively what is meant here is generating a number for which the least amount (although still a large amount) of primes remain to be checked. It has two sides. On the one side, you want numbers closer to 10k because they have less possible primes that need to be checked. On the other, you want to built it in such a way as to cross out the largest number of primes. At your example, you can cross out 6 primes from the list to get 15k. But at least 3 of those primes are <1 second trivial checks that are not worth explicitly crossing off, so at most I am giving you 3 primes you have meaningfully checked off the list (not that the check for, say, 11, isn't super fast as well). So that is 3 of the 25 primes less than root(10,000) that need to be checked...so you haven't made much progress. Excluding 2,3,5 as "trivial", you can actually use your idea of a+bcd for primes to make numbers with four exclusions (a+bcde is 17k for the minimum choice of 7*11*13*17). And there is a huge number of cases with 3 exclusions, you can find the "best" of these being whatever number is closest to 10k.
wall street quant interview question Quote
04-08-2014 , 03:53 PM
Quote:
Originally Posted by Aaron W.
I'm not sure how much "harder" it would be for that combination to not be a multiple of 17. The first and last products should probably viewed to be "random" with respect to divisibility by 17. (That is, 3*5*7*11*13+29*31*37 is equiprobable to have any remainder when divided by 17.)
This isn't quite true. The products will never be 0 mod 17, but should be viewed as random remainders from 1 to 16. Then adding them together will have a 1 in 16 chance of being 0 mod 17, so you don't benefit from extra terms.

This would suggest that the heuristic 2*3*5*7*11+13*17*19*23 (= 98887 -- prime)would be about as effective as 2+3*5*7*11*13*17*19*23 (= 111546437 -- not prime), but you would have more control in keeping the overall size of the number.

If you use subtraction, you can guarantee the value is a prime as long as the result is smaller than square of the largest prime you use in construction. But this doesn't help so much because you've got to basically go through the work of finding all of the primes up to sqrt(N) anyway to make it work.
wall street quant interview question Quote
04-08-2014 , 04:16 PM
Yes uke_master i agree its all crude for now but eliminating 2,3,5,7,11,13 improves the chance a number in 10000 to 99999 range to be prime by a lot.


In fact take a look at the general scheme i can imagine;


19* Prime[9 + n]*2 + 3*5*7*11*13 running it from n=1 to 100 gives 60/100 primes a decent 60% chance already.


Prime[9+n]= the 9+n th prime (just to give a scheme how to construct them using small easy primes) and produce the first 100 say .
(or one can replace 19 with 17 and use less first primes then try 23 etc instead of going for higher n int he above scheme and almost all these are still over 50% success rate).

The advantage all these have is that they can be reproduced within seconds and offered in some fast game like style.

If one has access to computers of course its trivial using Mathematica Prime[n] function for n>=1230 but we are talking basic calculators here or just pen and paper.


So all i ask is you guys to beat this with a similarly easy method.

The chance a random number in that range is prime is only ~9%. So 9% goes to 60% why not a small victory that beats coin flip.

All i wanted is an easy to apply method using a simple calculator that yields high % of primes. Obviously i can also pick an odd non 3x,5x number starting from 10001 and test them and settle to one that doesnt have a prime factor less than eg ~107 . But this approach takes far more time.

Last edited by masque de Z; 04-08-2014 at 04:25 PM.
wall street quant interview question Quote
04-08-2014 , 05:25 PM
Quote:
Originally Posted by masque de Z
19* Prime[9 + n]*2 + 3*5*7*11*13 running it from n=1 to 100 gives 60/100 primes a decent 60% chance already.
As n goes to infinity, I'd expect that 0% of the values are prime.

I've already given my heuristic:

Quote:
You can do a lot better by not picking an even number or a number ending in 5, or a number divisible by 3 by looking at the digit sum. You can look at the sum every other digit to avoid divisibility by 11. This will already reduce the candidate pool from 90,000 to maybe something like 15,000, so that you're up to about a 55% probability.
Here's a way to systematize this. Pick a 4 digit number ending in 1, 3, 7, or 9. Label the digits as bcde. Pick the first digit (called a) satisfying the following properties:

a + b + c + d + e is not a multiple of 3.
(a + c + e) - (b + d) is not a multiple of 11.

I think this would do comparably well as your scheme, except that the computational expense is much smaller. I don't need to compute the next prime to generate more numbers.

Edit:

Quote:
All i wanted is an easy to apply method using a simple calculator that yields high % of primes. Obviously i can also pick an odd non 3x,5x number starting from 10001 and test them and settle to one that doesnt have a prime factor less than eg ~107 . But this approach takes far more time.
I'll note again that the problem comes from generalizability. For any fixed range, you can come up with some heuristic. But making that heuristic do something for you in a new range may or may not be possible, depending on the number of candidates you actually produce.
wall street quant interview question Quote
04-08-2014 , 06:23 PM
Yes absolutely we agree that what i said is fine tuned for 5 digits (~60%) even say up to 10 digits wont be bad probably near >35%+ success rate (as a test suggested for an appropriately redeveloped similar scheme) for the number produced to be prime even up there but as you go higher it will continue dropping because the process eliminates only the first few primes as divisors and it grows real fast before using enough of them and lots of composites with bigger than eliminated prime factors exist, a situation that gets worse as you go higher.

However i maintain for the purposes i thought it first (ie typical less than 10 digit numbers its fairly good and in terms of using a hand held calculator faster than all other ideas so far seen even if computationally more intensive in terms of memory usage its effectively faster processed as done in real life by hand. Otherwise if we go to programming clearly we can start using advanced primality tests as well.
wall street quant interview question Quote
04-08-2014 , 06:37 PM
Quote:
Originally Posted by masque de Z
Yes absolutely we agree that what i said is fine tuned for 5 digits (~60%) even say up to 10 digits wont be bad probably near >35%+ success rate (as a test suggested for an appropriately redeveloped similar scheme) for the number produced to be prime even up there but as you go higher it will continue dropping because the process eliminates only the first few primes as divisors and it grows real fast before using enough of them and lots of composites with bigger than eliminated prime factors exist, a situation that gets worse as you go higher.

However i maintain for the purposes i thought it first (ie typical less than 10 digit numbers its fairly good and in terms of using a hand held calculator faster than all other ideas so far seen even if computationally more intensive its effectively faster processed. Otherwise if we go to programming clearly we can start using advanced primality tests as well.
I've been trying to figure out if there's a meaningful way to look at how one might view "success" for your algorithm.

Let's look at your formula: 19* Prime[9 + n]*2 + 3*5*7*11*13

This formula is guaranteed not to be a multiple of 2, 3, 5, 7, 11, 13, or 19 plus one more prime for all n. (You skipped 17, probably for no particular reason, but it would be easy enough to include.) I'm curious if this is any more successful than doing an Eratosthenes sieve for primes up to 19, and then just picking a random number that hasn't yet been crossed out yet. I suppose it might do slightly better because you're always guaranteed one more prime in your construction than the sieve, but since that prime is changing and has a computational cost of finding it, I would consider that to be a wash.

Maybe a way of making the comparison is to compare your idea against mine by picking out the same primes, so that you have a new formula like

3*5*11+2*Prime[n + 5] -- Or rearranged however you wanted to do it

(Notice that you can extend my scheme to any number of digits, so we can look in an unbounded manner.) If they are very comparable, then it wouldn't seem that there's anything particularly advantageous to your scheme. It's basically the same as just removing some candidates for small primes and picking randomly from what's left.
wall street quant interview question Quote
04-08-2014 , 09:39 PM
Quote:
Originally Posted by BruceZ
That's an easy one. One of the first things you check is sqrt(99221) ≈ 315, and 315^2 = 99225, so 99221 = 315^2 - 4 = (315-2)(315+2) = 313*317.
I should have said that it would be the last to be eliminated using the Malfeasance Wheel.

The real solution to masque's game (tm) is to just memorize a prime number between 10,000 and 99,000 or have access to google.
wall street quant interview question Quote
04-13-2014 , 07:53 PM
In terms of meta game, given you are supposed to solve it quickly it has to be non prime. I don't think there are any clever techniques to quickly be sure a given large number is prime, right?
wall street quant interview question Quote
04-13-2014 , 09:11 PM
Quote:
Originally Posted by dessin d'enfant
In terms of meta game, given you are supposed to solve it quickly it has to be non prime. I don't think there are any clever techniques to quickly be sure a given large number is prime, right?
Proving a number is prime can be done in polynomial time.

http://primes.utm.edu/prove/prove4_3.html

But you're right in that in the amount of time you're given, you're basically not going to be able to create a convincing argument that the number is prime, so you can expect that you're given a composite.
wall street quant interview question Quote
04-13-2014 , 09:18 PM
Quote:
Originally Posted by Aaron W.
But you're right in that in the amount of time you're given, you're basically not going to be able to create a convincing argument that the number is prime, so you can expect that you're given a composite.
This is assuming that the game is "fair." In such interviews, I would not be surprised if they give you a number that's prime and ask you to try to factor it in order to see what types of tricks/techniques you use.
wall street quant interview question Quote
04-13-2014 , 11:08 PM
My understanding of what i've been told by real experts is that there were a ton of probabilistic algorithms that pretty much always work and do so much quicker than AKS but you can't prove that they will always give a correct answer in P time for prime testing.

Just asked a friend who's an expert in this stuff and he wanted to add that there are other known algos that work in P for primality but always work only if certain versions of the Riemann Hypothesis etc are true. AKS was a breakthrough mostly because it didn't really on certainly true, but as of yet unprovable, conjectures.

Last edited by dessin d'enfant; 04-13-2014 at 11:35 PM.
wall street quant interview question Quote
04-23-2014 , 10:38 AM
Is an extremely stupid interview question.
wall street quant interview question Quote

      
m