Shortest "arithmetic" formula to output 1000 primes

Question

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.

Answer 1

Score 1164 883 835 772 601 574 554 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.)

Answer 2

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

Verification program Generator program

Answer 3

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

Verification, generation code (takes around 20 seconds to run)

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

Answer 4

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\$.

Answer 5

Score 1778 1319 1164

-459 inspired by Neil's suggestions!

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

Verification program, Generator program

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

---

Score 1635 1604 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

Verification program, Search program

Answer 6

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)

Verification, generation code

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.

Answer 7

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.