Interview Question

Junior Trader Interview

-

Jane Street

choose a subset from 1-30 that has the largest sum and the elements in this subset do not have common factors.

AnswerAdd Tags

Interview Answers

8 Answers

2

I don't believe any of the above have the exact correct answer, which I believe is 192. Summer is closest followed by Janed. Their errors, respectively, seem to be including 1 (1 is a factor for all the numbers!) and including 7 (which is a common factor of 28, also missed out 25, even though it was included in their sum to reach 199). WR describes some of the details I used, but I diverged mostly when using the "remaining" primes, 2, 7, 11 and 13: Lets say we start by looking at 2. Ask, "is 2 more efficiently used in 2^4=16, 2*13=26, 2*11=22 or 2^2*7=28". This is answered by comparing each of these to the individual uses of the primes: (Sum of Individual uses) gt/eq/lt (Combined use) 2^4 +13 = 29 > 2*13 = 26, so 2^4 and 13 is currently the best use of 2 and 13 2^4 + 11= 27 > 2*11 = 22, so 2^4 and 11 is currently the best use of 2 and 11 2^4 + 7 = 23 < 2^2*7 = 28, so 2^2*7 is the best use of 2 and 7. Therefore we keep 28, 13, and 11. The final list is thus 11, 13, 17, 19, 23, 25, 27, 28, 29 giving a sum of 192. As an additional note, above I've found the best use of, say X, by comparing "the sum of individual uses" it should technically be "the sum of the individual use of X and the current best use of the other factors", but this isn't a problem for the example above (and from what I've tried) the numbers up to 30.

GC on

0

The optimal sequence seems to be 1,11,13,17,19,23,25,27,28,29 which sums to 193. The idea is to list out all odd numbers and temporarily ignore even numbers(since they are all multiples of 2). In the list of odd numbers, we remove the smaller ones since we want to maximize the sum. As such we remove 3,5,7 and 9. We also remove 15(so that we can keep 25) as well as 21(so that we can keep 27). Now we are left with a list of coprime numbers. Next we seek the largest even number that has no common factors with any of the listed odd numbers. The largest such possible number is 28.

Anonymous on

1

Both of the above answers are incorrect. This might not be optimal, but 7,11,13,16,17,19,23,25,27,29 is better than Nov. 17. Here's how I arrived at my answer. First, any prime > 15 must be included as there is only 1 number with a multiple of that prime between 1 and 30. So 17,19,23,29 are included. Next, we have to use the primes 2,3,5,7,11,13. For 3 and 5, we could "waste" another prime to produce a product of 3 and/or 5 to produce a number under 30, but 3 and 5 have powers (27 and 25) which are very close to 30 that don't "use up" other primes. It seems reasonable that instead of picking say, 30, we could use 25 and 27 and use another number for 2. So let's add 25 and 27. Now the remaining primes are 2, 7, 11 and 13. Multiplying 2 and 13 gives a higher product than multiplying 2 and 7 or 11, but using 16 and 13 is larger than 2*13. So using these four, the highest we can get is 7, 11, 13, 16. All primes have been used, and our sequence is therefore 7, 11, 13, 16, 17, 19, 23, 25, 27, 29 with a total of 187. There might be a better one but I doubt it.

WR on

1

why use 1 instead of 28? that is the largest even number after all.... 2015 is wrong and 2016 forgot 7! so total set should be: 1, 7, 11, 13, 17, 19, 23, 25, 27, 28, 29 with sum of 200

an on

0

sorry i mean why use 16 instead of 28... aimed at WR

an on

0

answer is 199 1 is a common factor 27 28 would be chosen over 30 as 30 uses 2,3,5 as factors thereby, eliminating other large numbers 7 11 13 17 19 23 27 28 29

janed on

0

Also maybe 1 is not included, so you might include 1 to get 188. This is just a minor detail and I don't know if the question asks for numbers that share no prime factors 2-30 so that it is 187 or 188.

WR on

0

(Apr 28, 2015)'s answer is wrong. 30 and 27 have common 3. 11,13,17,19,25,27,28,29

Anonymous on

Add Answers or Comments

To comment on this, Sign In or Sign Up.