# Shortest “arithmetic” formula to output 1000 primes

Write a formula using only the digits 0-9, +, *, -, /, % and ^ to output a 1000 distinct primes when given input (which can be used as a variable n in the formula) of numbers 1 to 1000. (Note that / will give the quotient as all arithmetic is integer arithmetic.) Solutions can use ( and ) freely and they will not be counted in the length.

The shortest formula wins! The primes only need to be some 1000 primes not necessarily the first 1000.

EDIT

Edited for clarity based on suggestions by Sisyphus and an earlier question on primality testing.

Symbols are meant to work with integers in the "usual" way as follows.

n : Represents a number from 1 to 1000 which is the "input" to the formula. It can be used any number of times in the formula and it will represent the same input.

0-9 : Sequences of digits (terminated by non 0-9 symbols or  ) return the number represented by this decimal representation. Negation of an expression can be represented as (-{expression})

+ : Returns the sum of two numbers

* : Returns the product of two numbers

/ : Returns the integer quotient of two numbers

% : Returns the remainder on division of the first number by the second number. This and / follow Euclidean division conventions.

- : Returns the result of subtracting the second number from the first number.

^ : Returns the power of the first number by the second number. Anything to the power 0 is taken as 1 including 0!

() : Brackets are used in pairs to encapsulate an expression that returns a number using the previous rules.

• May we use 0<=n<1000 instead of 0<n<=1000? – hyper-neutrino Oct 10 '20 at 5:22
• @RosieF the formula should be defined on n which is a number from 1 to 1000 that should output the 1000 primes – hyper-neutrino Oct 10 '20 at 5:59
• do the 1000 primes need to be in order; that is, should f(x)>f(y) for all x>y – hyper-neutrino Oct 10 '20 at 5:59
• Can we use negative numbers as exponents with ^? This would allow using rational numbers, which I'm not sure you want. – ovs Oct 10 '20 at 11:57
• Since the allowed operations suffice to compute operations in the class ELEMENTARY, as I describe in this answer, it should actually be possible to give a fully general formula for the n'th prime for any n, not just up to 1000. I suspect this would be shorter than hardcoding information for 1000 primes. It may also be possible to modify Lopsy's primality-testing approach to give the n'th prime. – xnor Oct 10 '20 at 12:37

# Score 1164883835772601574554 506

541^n*743^(n/2)*(-1)^(n/4)*17^(n/8)%2310+297999352693782350435634574256421873511169209139789986107407037031463672744907435566931682004950168827622126589004268258979810886896053712313147567393521260370898856430728936238509646240927399434529133911694916958518274696252190810912239170743768597920487389824644988723446125401158124982957878348425345764310640796665180984553241724855646631162669954988652785474199384658696484753453854147610893664426900411229033105555630617039087023847065224114331551958/67^(n%250)%67*2310


Try it online!

(OP hasn’t answered my question about the behavior of / and % on negative numbers, so this answer works under the floored or Euclidean conventions where (-1) % 2310 = 2309.)

• Can you explain the comment in the end? – Pedro A Oct 10 '20 at 15:27
• @PedroA It's not a comment, it's just that the integer division operator is // in Python 3. – Neil Oct 10 '20 at 15:58
• @Neil Which incidentally means that the real score is 775. – Arnauld Oct 10 '20 at 17:38
• Impressive. Since you import isprime in the header, you might as well use it in the footer : print(all(isprime(f(n+1)) for n in range(1000))). – Eric Duminil Oct 11 '20 at 8:51
• @EricDuminil I’m not sure how I lost that, fixed. (The set is important to check distinctness, though.) – Anders Kaseorg Oct 11 '20 at 8:55

# Score 424 193

(30*n+(1-(1/(2^(n*30+16)%(n*30+17))))*((1-(1/(2^(n*30+22)%(n*30+23))))*((1-(1/(2^(n*30+28)%(n*30+29))))*((1-(1/(2^(n*30+12)%(n*30+13))))*((1-(1/(2^(n*30+6)%(n*30+7))))*((1-(1/(2^(n*30+40)%(n*30+41))))*((1-(1/(2^(n*30+18)%(n*30+19))))*(882)-22)+34)-6)-16)+6)+6)+17)+(1/(1+(n-475)^2))*10


This code searches the first Fermat pseudoprime of the form n*30+d, with offset d from {17,23,29,13,7,11,19,1}. The 4 cases where this fails (nothing found or pseudoprime found that is not a prime) are fixed a posteriori.

The order in which the offsets are testet was handcrafted as to minimize the number of pseudoprimes.

The following building blocks where used to yield boolean values: 1/t yields the truth value of t==1 (when we know that t is positive), 1/(1+(n-t)^2) yields the truth value of n==t.

b1*t1+(1-b1)*( b2*t2+(1-b2)*( b3*t3+(1-b3)*(...))) mimics the code

if b1: t1
else if b2: t2
else if b3: t3
...


Edit: I could't resist to optimize. Key tricks:

• the if-else now returns only the offset, the final result is call afterwards.
• xnors latest if-else gadget vastly reduced code size
• the resulting nested expression had adjacend summands that could be contracted
• no Fermat test for the last index, as on failure it must be corrected anyway
• grid offsets reduced the number of faulty cases to 1
• Very nice for a first answer! Unless I'm mistaken, you could probably use 0^((n-t)^2) for finding a truth value since 0^0 == 1 and 0^a = 0 for a>0 to make your approach even shorter. – Sisyphus Oct 12 '20 at 12:03
• You can get a prime by adding n//12+31739 to all faulty test cases. So the last part becomes +(1//(1+((n-360)*(n-523)*(n-654)*(n-941))**2))*(n//12+31739), for a total score of 408, I think. – Arnauld Oct 12 '20 at 14:52
• Great solution! I have an idea for a shorter if-else gadget replacing b*t1+(1-b)*t2 with (C*t1+t2)/C^b%C for solve large C>max(t1,t2), say C=9^9. This can then be recursively expanded to a sequence of if-else's by replacing t2. My hope is that since we now write the condition b only once, it will turn out shorter overall despite the longer "gadget". – xnor Oct 12 '20 at 20:21
• Another alternative to b*t1+(1-b)*t2 or (C*t1+t2)/C^b%C is (t2*(C+1)-t1*C)%(C+b). – xnor Oct 12 '20 at 20:44
• Or, maybe in your case it's best to just change b*t1+(1-b)*t2 to b*(t1-t2)+t2, and make the repeated t2 be the short alternative. – xnor Oct 12 '20 at 20:59

# Score 2341

This outputs all primes between $$\31\$$ and $$\8017\$$ (included).

(113467395935668970410160492737179506361846013862444084170197806945186405092696909126164158205176795679626257477170011681151081828693721528545308301463032313852735898720278373462178435545407324698821351304548663895918208828677426209417450978147368548225197577994423342074325769235860896833550745001703798952436205556087566508085462913775782980107289038262897153290911775461849717826677653709482106939563942394004153958440037041024098156603769869491411749714891362691603370984320936124882165280605174558859749487518953604842331779664328074931195219441658740089199947350409773050270253672458490842517716227535564556430387611590820439097600165832489226127768727315594781312368235772273799332206758908020271761747844563774441691210056862686595288936465304647859214996600265632129456351742413141396515373657806301978324762068082957610010981667490015017872109960968210719664738068557705903476757448731528153247317383397296951323720188125875523771873472067739298722926939700395850510069970848932566438053043914675253394668929358649440219868955587507427792258737478621439222869420782804120723724037942099140240986671113771843292946536125599661698395893047644516938416344212452574005345276922734768543821803294119263624051859444984143612848763146503016281898460776934493046854691490177334701465551154370051389269555217280444180285443508781807182786653180547028418689044382239111057385640034581765695611964566960423155654254631533264137376719604736646235721281638954806708051896372829794828522441565514326091912749474754904829505420000828614379978905433227551134966163328596138390836978449350464146519410700211096728982452219157828903470370081269726761212190236152174162025868830122533316205222356743692764196532590297434905214324476315471045728469350713970766245611550719074621408922145054478879292926089731205325210583591485438579344315785755440427094785080423582680705622279978441230497635622038519006130677863238128994042483893669828145180491933002965357145427263569009059259792273674006429955369804616413369843446578638589803530417606529429534136839003463278401805099943786536199970623822629008628461486362852575470843011844101058219237624888472496428195993935156341808156330726437453034634118080653972710684434727685175583816599255076497400463324245086662776394809313991656593421958024921754700582702681454016857120679602782/(208^(n-1))%208)*2-389+n*8


Try it online! (Node.js)

### How?

We compute:

$$a(n)=d(n)\times 2-389+8n$$

with $$\0\le d(n)<208\$$.

The values of $$\d(n)\$$ are extracted from a large integer, using base $$\208\$$.

Below is a graphical representation of $$\d(n)\$$. The minimum is reached at $$\n=399\$$, for which we directly have $$\a(399)=8\times 399-389=2803\$$. • How did you arrive at this formula? – Jonah Oct 10 '20 at 14:55
• @Jonah This is essentially trial and error + a small script to make sure that starting at 31 was optimal. – Arnauld Oct 10 '20 at 16:46
• I note you say "all primes between"... since the problem as stated doesn't say anything about coverage or ordering how far can you improve your expression? – Mark Morgan Lloyd Oct 10 '20 at 20:54
• Whenever I want to feel stupid, I look at your golfing answers. – Eric Duminil Oct 11 '20 at 8:52
• @Arnauld I know, and I applaud everybody's ingenuity. – Mark Morgan Lloyd Oct 11 '20 at 10:16

# Score 163,162

1%(4^(n*15+701)%(n*30+1403))*(1%(2^(n*30+28)%(n*30+29))*(1%(4^(n*15+6)%(n*30+13))*(1%(4^(n*15+9)%(n*30+19))*(1%(4^(n*15+5)%(n*30+11))*(1%(2^(n*30+6)%(n*30+7))*(1%(2^(n*30)%(n*30+1))*(16)-6)-4)-8)+6)-16)-1374)+n*30+1403


I would have posted this as a comment, except I only have 1 reputation

This answer is based on Max Kubierschky's solution, with many of xnor's improvements (specifically everything in his generation program with the addition of his trick to shorten expressions within powers).

The main optimization is based on Max Kubierschky's comment, and I found offsets (1403, 29, 13, 19, 11, 7, 1, 17) which are mostly small (with the exception of 1403) and have no faulty cases (these are just the previous offsets + 30).

## Explanation

This method works by generating primes of the form 30*n+(30*k+o) where 30*k+o is the offset composed of o, the base offset from the set {1,7,11,13,17,19,23,29} and k, the grid offset in the range -1 to infinity. The grids are the sets of integers n from 1 to 1000 for which 30*(k+n)+o satisfies the Fermat test for base 2. The prime grids are the sets of integers n from 1 to 1000 for which 30*n+(30*k+o) is prime.

The grid offsets were generated by first considering only prime grids (ignoring possible faulty cases) in order to find a set of grid offsets to cover the numbers from 1 to 1000, (in this case they were found by setting all except one of the grid offsets to 0, and varying the remaining grid offsets in the range from -1 to 66)

After finding grid offsets that cover the set, the code runs through all the permutations of offsets to find an order of offsets that covers up all the faulty cases (for the offsets used in the current formula, there are 81 that work), and then generating the formula using each to find which one turns out smallest

• Welcome to the site! I think combining aspects from two different answers is sufficient to warrant a new answer, but you can be the judge of that in the future. – Wheat Wizard Oct 14 '20 at 18:24
• You are very welcome. This feels more like a collaboration to bring this down than like a competition. How did you find the offsets? – Max Kubierschky Oct 15 '20 at 7:50
• You can still reduce the score by one by factoring out the minus sign from (-6) – Max Kubierschky Oct 15 '20 at 8:19
• @MaxKubierschky You mean something like this? 1%(2^(n*30-2)%(n*30-1))*(1374-1%(4^(n*15+686)%(n*30+1373))*(1390-1%(4^(n*15-9)%(n*30-17))*(4+1%(4^(n*15-7)%(n*30-13))*(2-1%(4^(n*15-6)%(n*30-11))*(8+1%(32^(n*6-4)%(n*30-19))*(4+1%(8^(n*10-8)%(n*30-23))*6))))))+n*30-1 – Neil Oct 15 '20 at 23:28
• @Neil: Yes, something like this. That brings it down to 162. – Max Kubierschky Oct 16 '20 at 13:22

# Score 17781319 1164

-459 inspired by Neil's suggestions!

(28389416454731914904646197269110195258968918334324648337536406183122452341375087148095278619811035121264892162819521481008101705277372014120459537607320900170581458493476732106029764703970199356551116634482447603151892501883985471668745077729919867085592433543835805593713705073935219732297479335704578859520285745463599513991638068362975801056573234819165907183812641577379596655404026370719245188577913240916435487946831490476753322022399310328082542064590520714793222945825868990061383486920959013849054510725156607978917228480666383141633344797723352686825873369593489365635288158535711600587674466307031798274562517630853907709405080966507256977400682764885616947585079339593770144096628672186322100621135207302538190833576961188067354198288862669754543325834368496102584439249310678425485967421525911011440604945657742285226023738594503000443799738987162853276495354222398842865644351430245057910519732921873667017428523263018326208740011108682459267993023371456176948637898475810086660149605871207027333515638814123020249096374464098648830557815605475878366999652657721355174060931879798441836550660645385542381428064142926776728816247052/(14^(n-1))%14+17*n)*6-1


This only considers primes of the form $$\6k-1\$$, and yields the lowest such prime larger or equal then $$\102n-1\$$.

# Score 16351604 1572

The rules don't explicitly forbid this, but it I'm not sure if this is intended. Similar to the above, but finds the next prime after $$\\lfloor n^{1007 \over 621} \rfloor\$$.

16921707110807543794883034080662369959145330548686331531608873466161289588508225504395036067059456808254955842748011935275567235182962066696532824341658478313282515740212407513889626921371569995949618530076057857935444678903541507451833650971208966857022879588416744784446458319742198436165114149099979782639487537376816458053319371322652945071076875723112404278546530735706274859341438493065587724231536852995916148117098900150719957460662049351379626720184420298531075385276847667099516667910747707987556366430526973567431116704034575028503641091403375164564764095445312182120994347975065105984011801750777939791614004132127064169527985645152866679765959804131578103751126570294714529430395223496169502308685883689716858687150949295161789378929626842080159238203320971831181073359220269422355146095712138282898528757872049694061460608989183240128781928642651093781146703726149529559745625017336481225823115996890606949461379145867395915059579445847541041812545106491388887871854979774599921555206338249335536406513747513391059876604297546812682955845160908578873034957552441194311592692169821206761814295401029352512438888121121058993809853128792382425425507315758921975340564810424303160455069096558687026616771028629060280318800048984850429104924036193703515227460262324051154267318767728375732829596082819890956884172016068499243733410402170378286724312471419805200183238726658173781500929626384453831442841099333236763065428542599128063204447946777048377374390957947246087390567878387147899066382490069914521762754275957918350785590249135/35^(n-1)%35+n^(1007*(621^-1))/1+1

• You can easily reduce the score to 1536. Instead of adding at most 58 to n², add at most 65 to 2n²... but you're always adding an odd number between 1 and 65, which you can encode in base 33. – Neil Oct 10 '20 at 18:42
• Better still, I've got it down to 1481. Add an even number between 0 and 56 to 2n²+9, which means you can encode in base 29: ([1463 digits]//29**(n-1)%29+n**2)*2+9 – Neil Oct 10 '20 at 18:45
• Actually, you don't even need to resort to n² - add an even number between 0 and 38 to 58n+1, which means you can encode in base 20: [1301 digits]//20**(n-1)%20*2+n*58+1 for a score of 1320, I think. – Neil Oct 10 '20 at 19:07
• @Neil your last suggestion looks more similar to Arnauld's answer than mine ;). I got inspired by your comments to rethink my answer and got a similar score by only considering primes of the form $6k-1$. – ovs Oct 10 '20 at 21:48

# Score 194

1%(2^(n*30+16)%(n*30+17))*(1%(2^(n*30+22)%(n*30+23))*(1%(2^(n*30+28)%(n*30+29))*(1%(2^(n*30+12)%(n*30+13))*(1%(2^(n*30+6)%(n*30+7))*(1%(2^(n*30+10)%(n*30+11))*(1%(2^(n*30+18)%(n*30+19))*(-18)+8)+4)-6)-16)+6)+6)+n*30+17+702*0^(((n-360)*(n-523)*(n-654)*(n-941))^2)


This is golfing down the excellent solution of Max Kubierschky, who said they will no longer spend time updating their answer. See their answer for an explanation of the strategy. The formula here is largely the same, but was shortened by removing repetition and introducing cancellations.

Branching

The main improvement is the arithmetic formula used to branch on a condition:

if b1: t1
else: t2


Previously, this was done as b1*t1+(1-b1)*t2. This meant the condition b1 needed to be repeated twice, which was costly because the condition of Fermat-primality used a relatively long formula.

We instead regroup b1*t1+(1-b1)*t2 into b1*(t1-t2)+t2. Instead of repeating the condition b1, we repeat the output t2. So, we arrange to make t2 be short.

As used, one of the branches just gives a number (the successfully found prime), which the other branches into further conditions to continue the search.

if b1: t1
else:
if b2: t2
else:
if b3: t3
else: ...


Our method has the no-result t2 repeated twice rather than t1, but we can fix this by negating the condition b2 so that we can interchange t1 and t2

We make it so that the twice-repeated t1 is just a number, while the once-repeated t2 is the long branch. We do this by negative the condition b to checking non-primality rather than primality. This is done by replacing the 1/stuff check for stuff==1 to instead be 1%stuff for stuff!=1 (in both cases, we know stuff!=0).

Doing this recursive expansion, we further find that it has terms like t1-t2 that subtract two potential outputs. These can be simplified. Because each possible output has form 30*n+d, we can cancel like (30*n+17)-(30*n+23)==-6, saving many instances of writing 30*n+.

Error fixing

We use a variation of an idea suggested by Arnauld to fix the faulty cases in a shorter way, using 32 characters not counting parens.

+702*0^(((n-360)*(n-523)*(n-654)*(n-941))^2)


There are four non-prime outputs, and a brute-force search finds that adding 702 to each one makes them prime and distinct from all other outputs. We use an indicator function of being in those four cases, and adding 702 times that indicator. The indication function uses 0^ to check ==0 for a product of n-k for each failed input k. (If we can't rely on 0^0==1, we can use 1/(1+_) as a slightly longer alternative for 0^_.)

## Potential improvements

Other potential approaches might hide errors in a more efficient way by adaptively adjusting the numbers checked and the base of the pseudoprime, as suggested by in comments by Max Kubierschky.

## Score: 181

1%(4^(n*15+8)%(n*30+17))*(1%(4^(n*15+11)%(n*30+23))*(1%(4^(n*15+14)%(n*30+29))*(1%(4^(n*15+6)%(n*30+13))*(1%(8^(n*10+2)%(n*30+7))*(1%(4^(n*15+5)%(n*30+11))*(4-1%(4^(n*15+9)%(n*30+19))*9)+2)-3)-8)+3)+3)*2+n*30+17+702*0^(n%941%654%523%360)


Verification

This includes some hand-found optimizations. First, the faulty cases are checked in a shorter way found by Sisyphus, as 0^(n%941%654%523%360). This evaluates to 1 exactly for the exceptional inputs n of 360, 523, 654, 941 and zero otherwise. This mod chain works because each value happens to be less than double the previous one, including if we append 1000 to the end.

Other misc fixes uses that some values could be written shorter in base 10. Some of the expressions within the primality checks like 2^(n*30+16) could be shortened like 4^(n*15+8). The various difference values were all even and could be written halved with a *2 later. A +stuff*(-18) was changed to -18*stuff.

• Amazing how short it's gotten, nice work! I believe you can just write 0^(n%941%654%523%360) for the error fixing condition (verify). – Sisyphus Oct 13 '20 at 9:29
• Absolutely amazing! Since there is a law of diminishing returns, one can imagine that it will not be substantially beaten. – prime_directive Oct 13 '20 at 18:33
• Nice work. Against my promises, I couldn't resist and did optimizations myself and came to very similar code. I didn't notice your answer, so I posted mine, sorry. You might want to integrate my improved offsets with only one faulty value. – Max Kubierschky Oct 14 '20 at 14:31

# Score 3627 3611

-16 thanks to ovs

3+2*((673353961358307057272173964285854305022400426862712283607156657501677042657259951223221803215027383567602764647222388720899640048400919228204711994106584574819864931142671077276501015670240042908527525811814749482980228611256604904077801987663433451736668942035070032934698860829734874720469210161714878816011028172504741493933579809209910574296450420677024369299112300880495910602256708103075450576078270852444355116728596095883942463207003664230806032583002863238578022990852754983925220712751300313297384933847995017349232355819646993088732601141789442882215894245107446410040144336314519163731984860252867369601943162930927332772671777942282743699929467221065940282853778104585857297151693682829776011636408160070741255197392398379178628552688459418297270015040378809673826532754044991491047949801618973677882844224163396790251399862833397713210556181592058088280808086833457843140471319676974659849432132663508730287070561924395375776930976500890901210246692236611967263433823329001222292758613681022886491412907860270659758688163330174276013329990329027854152360352827518702283024606693537791396445418370900593234237528394888627532943238538996362251812152746408784587329522604812362612961371495908130917050336369858923800623610558102111936921275925428797115215197211803311011792800756612190446912977181671053858030216650244322510913097098308798280996846215666363104582951499187555401911800510241478422010155586326948174226637924523831893487438486345918123442987712606546163773523778000231233612013623430096825956978942500937017215764165647469497368906623052990700252559013399879211291330909786175176769030687149835775829911173638805247625058275472816919156779291864013317155789882424054286324759552057921576616305056718594449895582860551963359519586408623708864584561224246719261364576172798288646507616917260121960060868716498458065082069151627356119717481764663140004551411443836333454961570935788652411333156384108866105400945838983456882978708424835088504807894682236883745784973974040648206299840824904279658635709233240664508551436734587146655032803436637243796714343511860088974399527943200654250140528821734417790449393945285632254377776046148129706540302453728840180914936819379438129581929627122804300127402709137830767613859849789109693350209773812357814726116008525681439255652001075856620439770299106395170302718499156517954285958747428744867003478259930463719139124320607133501439062288308905310881240867020273433661589445461066595657102669091317184108354554780017050349715850637537754106644755877075976187792445454821491839099929811225904639357052860836725499598183388404838427261429247485564633277253719915506486176500112852688184110139443587654583288837334797167835735314125201482147157537170750071301166473892100288867902409680472473344928486818014572141062729317739432887663007563551474290116952695377398184560337726343710669752174924005456400102600864172580302332762119194992885413026313261935677976382585514252800149731204021813826627080668911910552674815596682803932260276187920122242385797617877679445263885318204673888387270960551456287016730721644217841772314017713996319546205478449021962852317888766140480391183821928016315770425629570172282014425326824523667359350036132550758310731296339346026078740156028410312853179295874487323332796505227759163992369277010277291451843685489537975456773437258824811891298037075841518405314798557707912615382278504559764233167102285790740913352590724521945879074542935442272119863497621828348597890290006456761410388942801963190048896271350965485295433493478609534842891151210843278069634083290205578635819949175811191179//(3963**(n-1)))%3963)


(Brackets added for clarity, but not counted in score).

This unpacks primes from a large number. There are 13 bits in the largest prime, but we can omit the last bit if we ignore the prime 2, since then the last bit is always 1.

You can also check the verification program.

I do not consider this anywhere close to optimal, but it's a good starting point.