Prime numbers

[mmmcannibalism]

I am currently trying to work out a pattern for all prime numbers using just first year calculus knowledge and lower(lets ignore how impossible this sounds).

Basically, I have worked out a pattern that I think could be useful in working out very large prime numbers; but I am not sure how to confirm if it is original.

Does anyone have a list such as the k2^2 plus or minus 1 method of finding possible primes?

thanks in advance for any help

[t0rajir0u]

To my knowledge, the fastest known way to find large primes is to test them essentially at random (after, say, avoiding divisibility by the first few primes). What's your idea?

[mmmcannibalism]

I don't want to say anything specific since it might be original and useful(sorry if this sounds sorta mean)

I will say its the same type of thing as k2^n+ or - 1 where it finds lots of prime numbers but also gives some composites.

Basically, if this works at really large values; then I could say there is a prime number close(meaning within 100) of a million digit number.

[ElvetPuff]

It sounds like your closing in on an already discovered forumla: http://en.wikipedia.org/wiki/Mersenne_prime

[gmalivuk]

I don't want to say anything specific since it might be original and useful

I bet you a thousand dollars that it's not.

[mmmcannibalism]

It sounds like your closing in on an already discovered forumla: http://en.wikipedia.org/wiki/Mersenne_prime

While I wouldn't call what I found better then Mersenne primes; my main reason for thinking it is useful is the fact that a. it finds most prime numbers b. I think if if works for large numbers it may be able to find higher primes then mersenne without too much more trouble

I bet you a thousand dollars that it's not.

You would probably win; then again you might not and I'd rather be safe

[stephentyrone]

I bet you a thousand dollars that it's not.

You would probably win; then again you might not and I'd rather be safe

I'll match gmalivuk's $1k. You don't even have to pay me if you lose, I'll straight up give you $1k if you truly have a novel method for finding large primes. Get some more people on the forums to pitch in and we can establish the XKCD prize.

[mmmcannibalism]

I do really want to clarify; I don't really believe this is a certain method for finding primes but it is possible that it is(does that sound contradictory?)

Back to my original question

Does anyone know of a list of every current "system" that finds large prime numbers? For one I would like to compare it to make sure this isn't something that already exists, and of course it would be interesting to view.

Can we just make a truce about this being unlikely to work? I promise I will post what I found if it gets anywhere.

just fyi I did some quick hand testing and found 1069 and 8369 using this method; I realize they are hardly large prime numbers but it verifies this is at least casually amusing.

[Josephine]

I bet you a thousand dollars that it's not.

You would probably win; then again you might not and I'd rather be safe

I'll match gmalivuk's $1k. You don't even have to pay me if you lose, I'll straight up give you $1k if you truly have a novel method for finding large primes. Get some more people on the forums to pitch in and we can establish the XKCD prize.

with the brains roaming these fora, that might not be a bad idea.

[stormgren]

You may have stumbled across something like this:
http://www.maa.org/editorial/mathgames/ ... 17_06.html

Prime Producing Polynomials. The classic one is Euler's n^2-n+41.

[mr-mitch]

I had a dream about f(x) = 2^f(x-1) - 1, where f(x-1) = 2.
Of course, these are all, except f(x-1) mersenne primes.
Then you get f(x) = 3, f(x+1) = 7, f(x+2) = 127, f(x+3) = 170141183460469231731687303715884105727 (39 digits), which according to W|A is a prime.
Then of course, f(x+4) = 2^170141183460469231731687303715884105727 - 1, which W|A can't tell me is a prime, let alone evaluate the number.
How many digits is that?
W|A says it's also equal to 10^(10^37.70941922167128), so, ~10^38 digits?

I guess I'd use the lucas-lehmer test to check it, however, I don't know how!
It's a very, very large number.


Who wants to help me? Haha

[NathanielJ]

I guess I'd use the lucas-lehmer test to check it, however, I don't know how!
It's a very, very large number.


Who wants to help me? Haha

We can't help much. As powerful as Lucas-Lehmer is, it's nowhere near *that* powerful. I recall reading something that was said by one of the organizers of GIMPS that said something along the lines of "a million digit prime takes a couple days for a single PC to check for primality via Lucas-Lehmer, a 10 million digit prime takes about a month, a 100 million digit prime would take a couple years, and a billion digit prime would take 500 or so years".

Checking a proposed prime of the size you gave would take significantly longer than the lifespan of the universe via Lucas-Lehmer.

[mmmcannibalism]

You may have stumbled across something like this:
http://www.maa.org/editorial/mathgames/ ... 17_06.html

Prime Producing Polynomials. The classic one is Euler's n^2-n+41.

Not what I did, but that is rather interesting.

I have such a strange mind, for the past three nights I have "invented" a non perfect prime generator as I showered.

As a general question; currently all methods of finding large primes are imperfect correct? So hypothetically speaking what I came up with could still be useful if it generated some composites correct?

[NathanielJ]

As a general question; currently all methods of finding large primes are imperfect correct? So hypothetically speaking what I came up with could still be useful if it generated some composites correct?

It could be useful if there were a fast way of testing whether or not numbers that your method spits out are prime, or if you can prove some important/relevant theoretical property about your numbers.

If someone just came along and said "look! sometimes 2ⁿ - 1 is prime!", no one would care. The (main) reason Mersenne primes are important is because of the [url=http://en.wikipedia.org/wiki/Lucas–Lehmer_primality_test]Lucas-Lehmer primality test[/url], which can relatively quickly determine whether or not the given Mersenne number is prime or not.

[BlueNight]

Since there's a primes thread, I might as well pop in.

Does anyone know of any theory connecting primes to triangular numbers? I've got what appears to be a simple primality test based on triangular numbers. I've searched the Internet for half-hours at a time, and I've turned up exactly one paper that matches my conclusions, but doesn't take it this far.

[mmmcannibalism]

As a general question; currently all methods of finding large primes are imperfect correct? So hypothetically speaking what I came up with could still be useful if it generated some composites correct?

It could be useful if there were a fast way of testing whether or not numbers that your method spits out are prime, or if you can prove some important/relevant theoretical property about your numbers.

If someone just came along and said "look! sometimes 2ⁿ - 1 is prime!", no one would care. The (main) reason Mersenne primes are important is because of the [url=http://en.wikipedia.org/wiki/Lucas–Lehmer_primality_test]Lucas-Lehmer primality test[/url], which can relatively quickly determine whether or not the given Mersenne number is prime or not.

Okay, thanks for the help.

[Talith]

Since there's a primes thread, I might as well pop in.

Does anyone know of any theory connecting primes to triangular numbers? I've got what appears to be a simple primality test based on triangular numbers. I've searched the Internet for half-hours at a time, and I've turned up exactly one paper that matches my conclusions, but doesn't take it this far.

There's a strong link between Mersenne primes and perfect numbers. All perfect numbers have the form [imath]2^{n-1}(2^n-1)[/imath] which is a tringular number (it's the sum of all integers up to [imath]2^n-1[/imath]). That's the only connection between primes and trinagular numbers that I can think of at the moment.

[gmalivuk]

I bet you a thousand dollars that it's not.

You would probably win; then again you might not and I'd rather be safe

I'll match gmalivuk's $1k. You don't even have to pay me if you lose, I'll straight up give you $1k if you truly have a novel method for finding large primes. Get some more people on the forums to pitch in and we can establish the XKCD prize.

with the brains roaming these fora, that might not be a bad idea.

Note that my $1k was only based on how unlikely I think it is that someone with high school math would have come up with a novel and useful prime generating function. I'm not willing to shell out a grand for a novel idea in another field from someone who's actually doing high level research there, for example.

[BlueNight]

Since there's a primes thread, I might as well pop in.

Does anyone know of any theory connecting primes to triangular numbers? I've got what appears to be a simple primality test based on triangular numbers. I've searched the Internet for half-hours at a time, and I've turned up exactly one paper that matches my conclusions, but doesn't take it this far.

There's a strong link between Mersenne primes and perfect numbers. All perfect numbers have the form [imath]2^{n-1}(2^n-1)[/imath] which is a tringular number (it's the sum of all integers up to [imath]2^n-1[/imath]). That's the only connection between primes and trinagular numbers that I can think of at the moment.

How about trapezoidal numbers? No trapezoidal number of height>2 is prime; provable geometrically and tied to triangular numbers.

[t0rajir0u]

I want to warn the OP that most sequences that look like they're good at producing prime numbers for small values get steadily worse and worse at it at larger values, although it may take a very long time to see that this is true. Probably your idea falls into this category.

[Spacemoss]

The nth prime can be calculated using polynomials. I have a formula that generates any nth prime using a polynomial in polynomial time. Granted, it's a very large polynomial time, arguably impractical, but it exists. Each n generates a polynomial that generates all primes for inputs 1 ≤ n.

[gmalivuk]

What's the polynomial for, say, n=10?

[Spacemoss]

Hello, gmalivuk, thanks for your reply and question. I slightly misspoke, but still have what was stated, so first, I will correct the miss statement. Also, the phrase "arguably impractical" is most likely a gross understatement, in that the polynomials quickly grow over 100s of terms, however, the concept itself is sound, and how the terms are generated, is fairly easy to follow with a little familiarity. I will post the method and the first few terms. P.S. I can't post links yet as a new forums member, however, I do have formula pictures, latex, and pdfs that I can eventually share that make things much clearer more quickly.

So it does generate the nth prime using a single variable polynomial, however it's not that each polynomial gives primes for all input up to x, but rather the whole family of polynomials that does. In other words, the formula is for the family of polynomials. For example, if you want the 10th prime, you generate the 10th polynomial of the family, and then plug in 10 into that polynomial.

Also note though, that the Prime Polynomial that was originally mentioned by mistake, does exist and can be found with this method, however it is even more complicated, and I explain at the end. It's not too hard to see once you understand the other material.

Define F(x) = Sum[(1-(Product[x-kn,n=1..b])^2+Abs(1-(Product[x-kn,n=1..b])^2))/2,k=2..j] with b>=x, j>=x.

The output of F(x) is a polynomial. F(x) is equal to the number of factors of x, minus 1. The restrictions given on the indices b and j are the failsafe values, however lower values can be chosen given certain considerations.

Then define H(x) = (F(x)+1+Abs(F(x)-1)-Abs(3-F(x)-Abs(F(x)-1)))/4

And then the Exact Prime Counting Function, pi(x) = x-1-Sum[H(n),n=1..x]

The output of pi(x) is still a polynomial.

Then the x-th prime, P(x), comes from the family/sequence of polynomials:
(P sub s)of x = x + (P sub (s-1))of x - pi((P sub (s-1))of x) with (P sub 0)of x = 0, and (P sub 1)of x = x.

(P sub s)of x can be simplified further with the failsafe requirement that s>=x+1, however the bound is generally much lower the greater x becomes, and this failsafe works, but generates more extraneous computations the greater x becomes. Again, better choices can be made with understanding.

So at this point you have a family of Polynomials, (P sub s) of x, where the x-th prime is the x-th value of the x-th polynomial.

Lastly, if you want to calculate the Prime Polynomial, that is P(1)=2, P(2)=3, P(3) = 5, P(4) = 7, and so on, you do the following.

Take the Product Polynomial + 1, that is, Product[x-n,n=1..b]+1, and then just multiply it by (P sub (x+1))of x. The resulting polynomial will yield the n-th prime for all 1 <= x <= b.

All that said, the first few terms of a valid x=10 polynomial (there are more than 1) is:

Spoiler:

(1/4)*abs(-190737792000*x^27+235501883896356*x^26-230736832977530880*x^25+184177937298675005400*x^24-122024142260042480640000*x^23+68021348276040655759145610*x^22-32226747344878321105436966400*x^21+13074350787889252242007456884600*x^20-4567242047481630396326420273664000*x^19+1379180356950001840892273199547282020*x^18-360943829535533950891371711731439744000*x^17+81981216446656209378048315472132819396200*x^16-(1/2)*abs(x^30-2640*x^29+3334760*x^28-2683296000*x^27+1544795979804*x^26-677568974322240*x^25+235418865468844200*x^24-66512495832045120000*x^23+15565342758724261807590*x^22-3057964343190803749903200*x^21+509348797399185233996305800*x^20-72454565868457857446954592000*x^19+8848392406204444824863971979580*x^18-931061798551152374186648439432000*x^17+84599681977522581050679055121592600*x^16-6644378521128588192472688465463936000*x^15+450970466321563760815113965620825117665*x^14-26415853438464611650122769283244679342800*x^13+1332002065814556881503397411129054754914000*x^12-57598867734927412780137849228894203603520000*x^11+2124749357425556906781629164004269878259176544*x^10-66398477136317002816884971744242791635787778560*x^9+1741883362246262661693252983586381663609840541440*x^8-37910680596989664741105708124711295355277559808000*x^7+674001246443730184506702325125954906147176837058816*x^6-9587878286834403885169096803815710288740389191618560*x^5+106051301758758820427489765644517126218508885276467200*x^4-874892613027441767134857813149194732520743418953728000*x^3+5040728363191465133510590217922574745825754151034880000*x^2-18002111247440516975907328462980840841486402476441600000*x+29838691682509201983269850702992971758483722010623999999)-(1/2)*abs(x^30-1200*x^29+689000*x^28-252000000*x^27+65944777500*x^26-13147407000000*x^25+2076372065625000*x^24-266651775000000000*x^23+28364637782964843750*x^22-2532959755889062500000*x^21+191773448062751953125000*x^20-12399845374251562500000000*x^19+688322877883553217773437500*x^18-32921806442119716796875000000*x^17+1359725364321075003662109375000*x^16-48541607390058152343750000000000*x^15+1497563367499424941294097900390625*x^14-39873014657955400624694824218750000*x^13+913895720344464263130187988281250000*x^12-17963171266980442327880859375000000000*x^11+301199391488745499337362670898437500000*x^10-4278404295149852521351318359375000000000*x^9+51017608043414146865121459960937500000000*x^8-504707690453283346948242187500000000000000*x^7+4078649258281021217454849243164062500000000*x^6-26372754480945518458538818359375000000000000*x^5+132594741932393351791076660156250000000000000*x^4-497212876817335962158203125000000000000000000*x^3+1302141653728440724182128906250000000000000000*x^2-2113808779331394653320312500000000000000000000*x+1592573013831115722656249999999999999999999999)-(1/2)*abs(x^30-6720*x^29+21607040*x^28-44255232000*x^27+64853365054464*x^26-72406948069048320*x^25+64037348218952908800*x^24-46053290722213232640000*x^23+27433515101391172166615040*x^22-13718939243226894126651801600*x^21+5816593946032123076751340339200*x^20-2106127052933993092500091305984000*x^19+654709327967570113292613912813895680*x^18-175358979044616706918097676304121856000*x^17+40558658033867630658216269758425622118400*x^16-8108388675217306230769875273336490033152000*x^15+1400856469595644874460646773240652396694077440*x^14-208869742573374881955826553356923997119735398400*x^13+26809031790410761579443941669395573624763580416000*x^12-2950907007728103021615292527186072798153135882240000*x^11+277086029988908641449006988711724947811942818952249344*x^10-22040954026626040999193871411848848800495567740212346880*x^9+1471826733711247974210124693772827756479069849887975669760*x^8-81538842765136324881167200334697360588818907534811201536000*x^7+3690022447432937565355156323231495976006979241430056651718656*x^6-133615292536213459493381281206921576280147595503114551117742080*x^5+3761967198808184829414325361049285316035244425622199028468940800*x^4-78998545752646153251366079060967810689617797195380356563337216000*x^3+1158571891651124100387735065944523500976992718247638013868769280000*x^2-10532185037365363562755747288201390076732837405745012666059980800000*x+44436532506947275900241650518347407535745334566705291042226175999999)-(1/2)*abs(x^30-2400*x^29+2756000*x^28-2016000000*x^27+1055116440000*x^26-420717024000000*x^25+132887812200000000*x^24-34131427200000000000*x^23+7261347272439000000000*x^22-1296875395015200000000000*x^21+196376010816258000000000000*x^20-25394883326467200000000000000*x^19+2819370507811033980000000000000*x^18-269695438373844720000000000000000*x^17+22277740369036492860000000000000000*x^16-1590611390957425536000000000000000000*x^15+98144312852442312952650000000000000000*x^14-5226235777247530270680000000000000000000*x^13+239572279713979239794000000000000000000000*x^12-9417875137222642147200000000000000000000000*x^11+315830453129702800713174400000000000000000000*x^10-8972464124382103514856960000000000000000000000*x^9+213983357486924129852966400000000000000000000000*x^8-4233794969797936310476800000000000000000000000000*x^7+68428379594420481665822976000000000000000000000000*x^6-884922796883581694821785600000000000000000000000000*x^5+8898282503456082639851520000000000000000000000000000*x^4-66734782658766703853568000000000000000000000000000000*x^3+349540988595188085964800000000000000000000000000000000*x^2-1134842447153252597760000000000000000000000000000000000*x+1710012252724199423999999999999999999999999999999999999)-22565013074679514987249070358398922612064792997482398652248883200000*x-(1/2)*abs(x^30-4080*x^29+7964840*x^28-9904608000*x^27+8812438018524*x^26-5973580115455680*x^25+3207588736236541800*x^24-1400544454484410560000*x^23+506533972674014084685990*x^22-153793699176060627037754400*x^21+39589284000008297768269984200*x^20-8703308081091220681822841376000*x^19+1642627952840471977955784238278780*x^18-267121951449251929344527680410264000*x^17+37510775039929910408911393007858669400*x^16-4553002711470626621498223264874290048000*x^15+477581923921817330178839642209761033042465*x^14-43233526530499897103543683871593681374303600*x^13+3369125201992081484687415959994661305012146000*x^12-225155434803444582277788855805585585572692160000*x^11+12836080467854722372890848560108419193030483522144*x^10-619924898318650063468346802807806294572094229880320*x^9+25133690789749483535430414194619320634937682621064960*x^8-845385927715527599089534628443407682981389015619584000*x^7+23227922533537934352512794834874758318311285530756772096*x^6-510655974950841390849211219413408986971999079940077137920*x^5+8729274399334852462098642612539486106313457951695335628800*x^4-111294352622491870777511739659173937300437523174089457664000*x^3+990986889211793577990358651748259343795797094884410695680000*x^2-5469583938205840894158644781919030555613413880519815987200000*x+14010926783419024943413735805606745964002070254127742975999999)-(1/2)*abs(x^30-720*x^29+248040*x^28-54432000*x^27+8546443164*x^26-1022342368320*x^25+96875215093800*x^24-7464543128640000*x^23+476416994544722790*x^22-25526398400084181600*x^21+1159580706268921864200*x^20-44986273966336850784000*x^19+1498329082041603709365180*x^18-42998164039450323552456000*x^17+1065537415751501052181013400*x^16-22823534921988739975489152000*x^15+422479085309579841426741076065*x^14-6749169401501777505030493208400*x^13+92815209757634617216839739266000*x^12-1094603337301121436762070194240000*x^11+11012326973334093552927081731125344*x^10-93855143842282926897511559622842880*x^9+671502449663112255697639500387413760*x^8-3985829169585401821327739760347136000*x^7+19326195530998095410691141851079987456*x^6-74978500603590026816283991472628142080*x^5+226182402263528433046196608703697100800*x^4-508892590803845437932943981926383616000*x^3+799637665059400775575021570023137280000*x^2-778846653978150192051184231484620800000*x+352076358609106452909200719282175999999)-(1/2)*abs(x^30-2160*x^29+2232360*x^28-1469664000*x^27+692261896284*x^26-248429195501760*x^25+70622031803380200*x^24-16324955822335680000*x^23+3125771901207926225190*x^22-502436099708856946432800*x^21+68472081124473567159145800*x^20-7969183474314674105833248000*x^19+796273505689271916908740624380*x^18-68552961885868558197122307288000*x^17+5096432427879541236049169480784600*x^16-327492780006868684955476121556864000*x^15+18186339313656682061121165040609832865*x^14-871588836624551991789371212903168969200*x^13+35958513950940374885475870821066221074000*x^12-1272215280594697221836231433914357350080000*x^11+38397609909332860361820816470539925634958944*x^10-981757954508649941204599895430329991773744640*x^9+21072458400467647664506075042250409795906819840*x^8-375238628286151393113908906834078548045289472000*x^7+5458288445760965754135312524853141186453374382336*x^6-63528429514536929994832343563424768299591833661440*x^5+574925319283026785011213959505613722049707808563200*x^4-3880610060562322296149731236530588085549762772992000*x^3+18293144902733530920558485109320135261302320046080000*x^2-53452539771896901086604553629457051142844491366400000*x+72489400057790548363973345969624382942570676223999999)+96793725301324060193433803231382904470776234939040026445938687999987-(1/2)*abs(x^30-3600*x^29+6201000*x^28-6804000000*x^27+5341526977500*x^26-3194819901000000*x^25+1513675235840625000*x^24-583167431925000000000*x^23+186100388494032339843750*x^22-49856246875164417187500000*x^21+11324030334657440080078125000*x^20-2196595408512541542187500000000*x^19+365802998545313405606733398437500*x^18-52487993212219633242744140625000000*x^17+6503524266061407789190755615234375000*x^16-696519010070457152572300781250000000000*x^15+64465192460568213108328411264801025390625*x^14-5149207612229749683403391424865722656250000*x^13+354061926870859593264922101081848144531250000*x^12-20877901788732937560311702618408203125000000000*x^11+1050217339833649974148471997368368530273437500000*x^10-44753620072499717186694888888760986328125000000000*x^9+1600986599118977202648257018059286499023437500000000*x^8-47514786357705614821049448971118164062500000000000000*x^7+1151931019484883273285099378292559829711914062500000000*x^6-22345334471341975574578044257351202392578125000000000000*x^5+337038043534053017267877770518805236816406250000000000000*x^4-3791545262961428150035023554611083984375000000000000000000*x^3+29788824359305231853389053420094299316406250000000000000000*x^2-145071494202716311821934623920288085937500000000000000000000*x+327896660761075516146794631408691406249999999999999999999999)-(1/2)*abs(x^30-3360*x^29+5401760*x^28-5531904000*x^27+4053335315904*x^26-2262717127157760*x^25+1000583565921139200*x^24-359791333767290880000*x^23+107162168364809266275840*x^22-26794803209427527591116800*x^21+5680267525421995192139980800*x^20-1028382350065426314697310208000*x^19+159841144523332547190579568558080*x^18-21406125371657312856213095251968000*x^17+2475504030387428629041520370997657600*x^16-247448384863809394249568947550552064000*x^15+21375373376398389808054302570200384471040*x^14-1593549671732901626249897410254852272947200*x^13+102268340264933630292678610494215292452864000*x^12-5628408446747022670012078337070603939348480000*x^11+264249830235394135903365124427533099948828524544*x^10-10509945882142086505505500513004707718131812925440*x^9+350910838535129540970355199282843531722800695869440*x^8-9720187516824761018892192880475206445314753953792000*x^7+219942477192457769236275930597275255680500223721865216*x^6-3982046024090452775161900556293772944216358527633981440*x^5+56057679635408294639204820410151560843516058111521587200*x^4-588585032169864723469064228690920849812163391674908672000*x^3+4316016628038600461139288045259280133906724744467578880000*x^2-19617723370651460369593924448269214624041388567062118400000*x+41384745861354540940599190553973808452249816215322623999999)-(1/2)*abs(x^30-5760*x^29+15874560*x^28-27869184000*x^27+35006231199744*x^26-33500114725109760*x^25+25395256385549107200*x^24-15654281551313633280000*x^23+7992950823547635907952640*x^22-3426095197282133863091404800*x^21+1245090302624400396979588300800*x^20-386429150908625958073823920128000*x^19+102964390496230221489851792338452480*x^18-23638490667197746364725383741308928000*x^17+4686283113796661536795691033741072793600*x^16-803031745077703061298984955435196350464000*x^15+118917290698253235285440521932572155592048640*x^14-15197778400831879339035561197740025439269683200*x^13+1672010176315190745817647292070020439284383744000*x^12-157748965823610619114882550475573808229284577280000*x^11+12696348583318908356008421982074850714035636083359744*x^10-865660909229895048759483970415501102779659378009047040*x^9+49548135335217849991322047561927485183855866157874544640*x^8-2352818259611781582184964746464077198179414114232696832000*x^7+91265378016970531215771391607447063201331554491562119397376*x^6-2832607665489720045493723255831476967242906439311240399421440*x^5+68359436509710466996613173810421781524137762839710185763635200*x^4-1230426784866701895004706444350728987316800488180118120824832000*x^3+15467241914026630470411219757928149918102444472442651389460480000*x^2-120520682177874778264031010339259610430155462638093155591782400000*x+435849421208010876074917043036559366639986109381052333031423999999)-(1/2)*abs(x^30-960*x^29+440960*x^28-129024000*x^27+27010980864*x^26-4308142325760*x^25+544308478771200*x^24-55920930324480000*x^23+4758796548465623040*x^22-339968103550864588800*x^21+20591517191766854860800*x^20-1065138607157346828288000*x^19+47301187993575404265799680*x^18-1809895449525072647159808000*x^17+59801353946119192415148441600*x^16-1707905976201803201368817664000*x^15+42152661398963220785822894653440*x^14-897860469778531336373625107251200*x^13+16463281702395281103010748432384000*x^12-258876580557969665874785395015680000*x^11+3472592556218712000672485182321721344*x^10-39461314538244516663293228357611683840*x^9+376443503531874666640075971209975562240*x^8-2979268351303916614744270138037501952000*x^7+19260876552687433339848444008555668832256*x^6-99633449457413890994440023580966586941440*x^5+400743017668022180621169456011174687539200*x^4-1202186969258691063163562944520270118912000*x^3+2518708265580806169690368032363543265280000*x^2-3270960654159110526981893446387000934400000*x+1971509899306927861602641878475341823999999)-(1/2)*abs(x^30-1680*x^29+1350440*x^28-691488000*x^27+253333457244*x^26-70709910223680*x^25+15634118217517800*x^24-2810869795056960000*x^23+418602220175036196390*x^22-52333600018413139826400*x^21+5547136255294917179824200*x^20-502139819367883942723296000*x^19+39023716924641735153950089980*x^18-2613052413532386823268200104000*x^17+151092775292201454409272483581400*x^16-7551525416986370674120146104448000*x^15+326162313482641446045750466464239265*x^14-12157819150794232378005198747671907600*x^13+390122757968649407549585763909207506000*x^12-10735337155813260402702480959073264960000*x^11+252008276210207115081181644847424602459744*x^10-5011532727309268238785505539419511660638720*x^9+83663663514883408777798461743079073839855360*x^8-1158736648181052329408191785869026952423424000*x^7+13109593224075899674670453703241065483123077376*x^6-118674219372584008430299179443531422144662097920*x^5+835324520400290111291480368527048242740572364800*x^4-4385300220324581291296066557548350466878439424000*x^3+16078414872432501841855377127451003096650260480000*x^2-36540857275298722776759275138879594624119603200000*x+38542548065403980147651574159016654316568575999999)-(1/2)*abs(x^30-1920*x^29+1763840*x^28-1032192000*x^27+432175693824*x^26-137860554424320*x^25+34835742641356800*x^24-7157879081533440000*x^23+1218251916407199498240*x^22-174063669018042669465600*x^21+21085713604369259377459200*x^20-2181403867458246304333824000*x^19+193745666021684855872715489280*x^18-14826663522509395125533147136000*x^17+979785383053216848529792067174400*x^16-55964663028180687302453417213952000*x^15+2762516817442453637419689224007843840*x^14-117684367494811659321163790057629286400*x^13+4315750518592708569467649637058871296000*x^12-135725884667576800182159485181980835840000*x^11+3641277212229592154817151822538181280006144*x^10-82756374706508564609458720436622057988423680*x^9+1578918492637756041787137206349885340605480960*x^8-24991914325894845345776702434102493174562816000*x^7+323143886273772449628238752395444304023226679296*x^6-3343143804744231301228350149325939835798636462080*x^5+26893408671632897668289496544407904586310667468800*x^4-161354803645107358751717910798500705306658471936000*x^3+676110601802152809008447321575330494191165767680000*x^2-1756083629514518261729569742048612296596180172800000*x+2116892635315877057953640253812899869125246975999999)-(1/2)*abs(x^30-4560*x^29+9949160*x^28-13827744000*x^27+13750382957724*x^26-10417370024093760*x^25+6251824199111548200*x^24-3050911818581590080000*x^23+1233235491640611583269990*x^22-418485735523686100711240800*x^21+120399433375712363547012865800*x^20-29582565333902290631536419168000*x^19+6240154807313299912917233439150780*x^18-1134149780978145982320896278987848000*x^17+178000634989954139907741194296238760600*x^16-24147273581290523132003992384311963264000*x^15+2830888433278131071160324962532562386330465*x^14-286417938693121057933607948898787363599685200*x^13+24946026691446691481208379370343536465074754000*x^12-1863250928603584826883285228591802425156770880000*x^11+118720583502302410807041597268796800523542647298144*x^10-6408219077401825551099307455622992123614138666826240*x^9+290374997091270669011572739242890431901501512563511040*x^8-10915977818597172848346486340350685064774124631590912000*x^7+335214409382864681192059838718561648350822745641107312896*x^6-8236551288857421092506485604353365731702357213543203901440*x^5+157361981082504788814004194573223297494733442605553186611200*x^4-2242329735452741698195103181901028460677130394225411325952000*x^3+22315105113012488388058837185005273855366974805520434503680000*x^2-137654368758729800088759849835783944986172737588408165990400000*x+394100740448110086095972881718291820950714462315427201023999999)-(1/2)*abs(x^30-5520*x^29+14579240*x^28-24528672000*x^27+29526483968604*x^26-27078790724032320*x^25+19672165416292045800*x^24-11621155187298795840000*x^23+5686432593722000259703590*x^22-2335870569317506923339237600*x^21+813517301417136935072070544200*x^20-241964926345436340343785886944000*x^19+61785445813393224525379427381507580*x^18-13593630758881343162885606058676776000*x^17+2582621977788095476777446466823548637400*x^16-424113042760276037909762660968989620352000*x^15+60188083523874223105582971511969460076469665*x^14-7371607631341163245125143807655617045075600400*x^13+777208629219784683404274363782590483567683986000*x^12-70271918850111542897481921050886474307558328640000*x^11+5420142738515842170376091566938902618392060056360544*x^10-354157372455470564081585165935616864827943643545326080*x^9+19426402819590153992611493878221843415755043977177634560*x^8-884036203847828663330344241288133241859898716795283456000*x^7+32862781579263082397226846160406056048661612643829221110016*x^6-977465153346901329277984504582464554267961598608793762222080*x^5+22606322874164481727113602600836918972879978187208714170572800*x^4-389945419153779859965330623068971207403173564326259607044096000*x^3+4697616060489633737053131440356198933940301869831941208186880000*x^2-35078645548224825391427401979345153178927647746553892342988800000*x+121572207532316706402412826049676834921243381500090609893375999999)-(1/2)*abs(x^30-6000*x^29+17225000*x^28-31500000000*x^27+41215485937500*x^26-41085646875000000*x^25+32443313525390625000*x^24-20832169921875000000000*x^23+11079936633970642089843750*x^22-4947187023220825195312500000*x^21+1872787578737812042236328125000*x^20-605461199914627075195312500000000*x^19+168047577608289359807968139648437500*x^18-40187752004540669918060302734375000000*x^17+8299105006842498801648616790771484375000*x^16-1481372295839177012443542480468750000000000*x^15+228510035324008932692580856382846832275390625*x^14-30420695997585602283244952559471130371093750000*x^13+3486235505464417507668258622288703918457031250000*x^12-342620301570519300992600619792938232421875000000000*x^11+28724612378000783857094065751880407333374023437500000*x^10-2040102145743299732852610759437084197998046875000000000*x^9+121635456188712470209888124372810125350952148437500000000*x^8-6016584520975152813771273940801620483398437500000000000000*x^7+243106440203250719157150342653039842844009399414062500000000*x^6-7859693312926744955342655885033309459686279296875000000000000*x^5+197581562299122440503651887411251664161682128906250000000000000*x^4-3704524612555920795784913934767246246337890625000000000000000000*x^3+48508556698577132976879511261358857154846191406250000000000000000*x^2-393727566922343271471618209034204483032226562500000000000000000000*x+1483199199504326770693296566605567932128906249999999999999999999999)-(1/2)*abs(x^30-3120*x^29+4657640*x^28-4429152000*x^27+3013518064284*x^26-1562092859920320*x^25+641424087917269800*x^24-214169643989346240000*x^23+59233040459780488985190*x^22-13752714313297815725469600*x^21+2707210068645223932968104200*x^20-455117041088850984631560864000*x^19+65685934082793952771131552904380*x^18-8168403464492261966076497695416000*x^17+877158488557840509751082711555765400*x^16-81416864484540869632576728573370752000*x^15+6530685586888534087643377991218866752865*x^14-452091131659423358055908725776960417044400*x^13+26941198209643702149096913217521418975426000*x^12-1376818275532821939351270535398801612565440000*x^11+60023463207341899368131285974762675540872398944*x^10-2216777623518892834389501956971032219139255764480*x^9+68728006681181504072625760041688042982430346940160*x^8-1767774747087272744269862014118317957429965060096000*x^7+37142977159321292708872162376814185563218272528814336*x^6-624437808631325969201676358314995071599805097905582080*x^5+8162690870425217193873687271624177413699318087749836800*x^4-79583450089164613345915478448001310915693292939411456000*x^3+541891045796738390519031805997069682153536438709166080000*x^2-2287140205977357452894477194234579426841429165870284800000*x+4480224652725431217390196930599967028976416773963775999999)-(1/2)*abs(x^30-6480*x^29+20091240*x^28-39680928000*x^27+56073213599004*x^26-60368294506927680*x^25+51483461184664165800*x^24-35702678383448132160000*x^23+20508189443825203963471590*x^22-9889449750569431276636802400*x^21+4043207918319039667180400344200*x^20-1411716944924421573826042383456000*x^19+423172388137012356793898026161131580*x^18-109295563852763617310510628322326024000*x^17+24376078313142581466244860102338837477400*x^16-4699163443490018121638426008940136747648000*x^15+782862274446310682470787738698085145196285665*x^14-112557124430675014021654060101822943899029979600*x^13+13931065058586642047974380871198306869871185186000*x^12-1478646798363809425472202780132814526066213367360000*x^11+133884187267544841826308038826562488751674866214632544*x^10-10269534964015284703685298194498117392797453396328081920*x^9+661276073173248044835874774443487303310029437608663842560*x^8-35326157285541331129517902597068739166392198057476409344000*x^7+1541581875715867467263350925348346457886876923121516153999616*x^6-53826914703469634969391733553775003407305632367480056848977920*x^5+1461383022926665675272823172732584686923389310525917727346892800*x^4-29591970318039294656491505510863646124664338198962274209071104000*x^3+418488479288362716387734948829222939606076883428967405844602880000*x^2-3668467975656701396294437124689885067218875487003803676046131200000*x+14924924642760410647629037831615315041526345738896217501925375999999)-(1/2)*abs(x^30-6240*x^29+18630560*x^28-35433216000*x^27+48216289028544*x^26-49986971517450240*x^25+41051141626705267200*x^24-27413714430636318720000*x^23+15163658357703805180208640*x^22-7041389728408481651440435200*x^21+2772183110292709307359338700800*x^20-932079700149966816525436649472000*x^19+269049586003124030550554840696340480*x^18-66915561181120610026098669120847872000*x^17+14371364676531658911761739146129660313600*x^16-2667867815429435216120274241892212801536000*x^15+427995010622326969967796420032519651515760640*x^14-59256488808863938387104068505037755782843596800*x^13+7062473463468838656172861218493934855894073344000*x^12-721849300042552148938598926463166899848709406720000*x^11+62939162956101739471837631322272747267945816595103744*x^10-4648919626717893145425612808065714160432328504990760960*x^9+288266153334906307257830515845892325433379533892500848640*x^8-14829169385614272840764118650529034964240664342841786368000*x^7+623155750684999741175973384582884983058194613362784338968576*x^6-20952655987948840303411743651088136710330791370926196323778560*x^5+547788911497407522834130912289957981167819274443543863833395200*x^4-10681509857369071821287253597323702092125953323166247281491968000*x^3+145462769980764353171682379521326934792659615937511048064532480000*x^2-1227899048254931747085455011031919798824795355664179074275737600000*x+4810604590547171086547090571981610012032998599860060552167423999999)-(1/2)*abs(x^30-3840*x^29+7055360*x^28-8257536000*x^27+6914811101184*x^26-4411537741578240*x^25+2229487529046835200*x^24-916208522436280320000*x^23+311872490600243071549440*x^22-89120598537237846766387200*x^21+21591770730874121602518220800*x^20-4467515120554488431275671552000*x^19+793582248024821169654642644090880*x^18-121460027576396964868367541338112000*x^17+16052803715943904846312113228585369600*x^16-1833850078107424761526793575266779136000*x^15+181044302147908641581936752984578053898240*x^14-15425125416279953810543580290433585827020800*x^13+1131348103945966995234527546457160757018624000*x^12-71159452620594505413904032167090368460881920000*x^11+3818155894090856823329549789469795973863722450944*x^10-173552696728503849287855574481102822154538697359360*x^9+6622464149344510717091956733142149483642931212451840*x^8-209647372449516106826345212252331647064083034800128000*x^7+5421454779094515522262081248508886504567343015511719936*x^6-112177291462511586589338191557747094056396512859583938560*x^5+1804786105041032787547156936227140029407698844912923443200*x^4-21656675147132428007736494084281430472657243375201681408000*x^3+181492057701195311067863464619052479558910934018770862080000*x^2-942790219725729536415408804781243232008005745087453593600000*x+2272996159456236648366895393568886060203903972460724223999999)-(1/2)*abs(x^30-480*x^29+110240*x^28-16128000*x^27+1688186304*x^26-134629447680*x^25+8504819980800*x^24-436882268160000*x^23+18589049017443840*x^22-664000202247782400*x^21+20108903507584819200*x^20-520087210526048256000*x^19+11548141599993995182080*x^18-220934503115853594624000*x^17+3649984982062938990182400*x^16-52121154058892919963648000*x^15+643198568709765942166487040*x^14-6850131757953882876385689600*x^13+62802435693341373836558336000*x^12-493767891994418460607119360000*x^11+3311722332209312439606175596544*x^10-18816621083376177150389303377920*x^9+89751125224083582553881638338560*x^8-355156463540067269175561682944000*x^7+1148037704985584815731551886114816*x^6-2969308181327995389534235703377920*x^5+5971536303580137798505566358732800*x^4-8956990907033466273274741653504000*x^3+9382919466424011326172828794880000*x^2-6092638995794785259257803571200000*x+1836111675302430858465509375999999)-(1/2)*abs(x^30-5280*x^29+13339040*x^28-21466368000*x^27+24716735676864*x^26-21682207178311680*x^25+15066807390006028800*x^24-8513599466501775360000*x^23+3984727746233411022743040*x^22-1565677743713691519950438400*x^21+521573168536765679612217139200*x^20-148386950898601692051363004416000*x^19+36243015295813406002642829228359680*x^18-7627258253731040249337024015826944000*x^17+1386081189519729967934325639112173158400*x^16-217722995380341577890945055636322254848000*x^15+29554800480850002628779308850926394911293440*x^14-3462378741886433578204891615493446610819481600*x^13+349176349540891199144826610943014929672175616000*x^12-30198395167009623391672912696518484218882293760000*x^11+2227961182211860759085453582274941291865494303801344*x^10-139247699123381475091435952263382258964575611382661120*x^9+7305988353802948466990657762068294957205408622323957760*x^8-318017838541352277564557272020618169907644180425867264000*x^7+11307864495855693151188798356340372666690913585532560736256*x^6-321715809999861500425442267205051591415239754783699941457920*x^5+7116982386751506488868832544029772169068747064810039725260800*x^4-117426098764526435637145685283933442028501894562921509289984000*x^3+1353110216745434558422016165977185724589820412076940884705280000*x^2-9664809883338848014606849459404082261095652333126260306739200000*x+32039051232951059434300586978039355755134799145996361138175999999)-(1/2)*abs(x^30-6960*x^29+23177960*x^28-49168224000*x^27+74626381079964*x^26-86293895661005760*x^25+79044769773228316200*x^24-58876289744963820480000*x^23+36324629263017509676818790*x^22-18813960667998278462088208800*x^21+8261680819703824941716546785800*x^20-3098305220235232016556450173088000*x^19+997534964997054147102942501089013180*x^18-276724475873262836145008278893809208000*x^17+66289250522208113478661003396978872456600*x^16-13725685916651312977008622260112456673664000*x^15+2456026820310448130009502884563969981098388065*x^14-379275651424696488482302991950377608451493441200*x^13+50419731397777484994948712549626290030814776834000*x^12-5747975235023435007160958728200534116701216927680000*x^11+559002771873046820430153119820798202865823913959989344*x^10-46054247057055406877336162515504441504171699545689187840*x^9+3185194456956499830069894955783283025271416095670577770240*x^8-182761104608300136957314669924329881915289146122230167552000*x^7+8566199912440431471857964129220377248305180924909846755430656*x^6-321259020414045291605938679818422817694868200217249258516541440*x^5+9368156452105810101276909284784002983246527366012874731812659200*x^4-203750270353315314589078587889675550791625257305146052536205312000*x^3+3094867435786707827964427356185599596361858137674724334821089280000*x^2-29139192375749902026341282464384248810173527860366873579464294400000*x+127332468708622155727358481663540221439552451916690594464333823999999)-(1/2)*abs(x^30-1440*x^29+992160*x^28-435456000*x^27+136743090624*x^26-32714955786240*x^25+6200013766003200*x^24-955461520465920000*x^23+121962750603449034240*x^22-13069515980843100979200*x^21+1187410643219375988940800*x^20-92131889083057870405632000*x^19+6137155920042408793559777280*x^18-352240959811177050541719552000*x^17+17457765019672593238933723545600*x^16-747881592323727031516828532736000*x^15+27687589334848624487742903160995840*x^14-884627131793640981139356805811404800*x^13+24330950346705369095691236610146304000*x^12-573887394506930355837112257997701120000*x^11+11547261768390770481354067653296488710144*x^10-196828502619131324708970162286164191477760*x^9+2816485410631790386521632147032931083223040*x^8-33435558458617458401604448375566067826688000*x^7+324239756881789742293773996122208782826602496*x^6-2515860999965120510685177684556880854709698560*x^5+15178844072696421773430313930757625034781491200*x^4-68302407333725828342524757605432272195944448000*x^3+214651101254995514278234577358996786307399680000*x^2-418140113429397921679494429037167482870169600000*x+378039111480220065756895286704155628929023999999)+2765079559797464013461284657654802306513973735*x^14-409566602428625758396213437135900088247119929600*x^13+52380120213380061462035796176061807855023548318000*x^12-5760243847834203423736171534002208859793887984640000*x^11+541684057220526473034497566766882760935192057286609056*x^10-43246690693179947305695834091798061245824176383812280320*x^9+2904207457701584278251050348476044230751216995073610625280*x^8-162093255866027760648022376840415651140041067189435990016000*x^7+7402404939243885587099395260632990148581095839555198433761024*x^6-270893314035631266135802099384786290908743982492052385670430720*x^5+7718943603455697962168806532451198682489259346490874831266406400*x^4-164254958659602217391317328177056746069862025025360839708246016000*x^3-(1/2)*abs(x^30-5040*x^29+12153960*x^28-18670176000*x^27+20520010036764*x^26-17182508184354240*x^25+11397272180570476200*x^24-6147372241789571520000*x^23+2746449166568412484514790*x^22-1030082249162425831203031200*x^21+327552848738909564551439185800*x^20-88952562581562536801603716512000*x^19+20738803146148528371950389769061180*x^18-4166049563100195557233426594409592000*x^17+722672060346565498194463601522845176600*x^16-108356135916473653070477283279136638336000*x^15+14040218109201804670967973565505964117700065*x^14-1570062746858088748755468981121746017984938800*x^13+151141549662242800142420808401143723576990434000*x^12-12477268711455127613697996284032059892889296320000*x^11+878698526412649565844276007901522128880261609653344*x^10-52422402416048829593166131699241131560058083777820160*x^9+2625454411867874709541207363748070459369013572098154240*x^8-109087151483107393720520310375780295982481226655643648000*x^7+3702536337730214714680234935832344051803019071577977753856*x^6-100551314308930236420607180939173669210226965731743902658560*x^5+2123282853970808082389826342906647663175108835107918362419200*x^4-33440534331020064075721117974846460220878674916309828927488000*x^3+367822560041396587452505827098618321315659725601879318241280000*x^2-2507812824040081756970299753980288527160304785939039574425600000*x+7935568854998449141747931062176960806667757782676931149823999999)-(1/2)*abs(x^30-4320*x^29+8929440*x^28-11757312000*x^27+11076190340544*x^26-7949734256056320*x^25+4519810035416332800*x^24-2089594345258967040000*x^23+800197606709229113648640*x^22-257247283050934756573593600*x^21+70115411071460932770965299200*x^20-16320887755396452568746491904000*x^19+3261536279303257771658201597460480*x^18-561585863769035228750825941303296000*x^17+83499948898378403611429592773174886400*x^16-10731283415265073068621041551175319552000*x^15+1191859933259804315557636672101406006640640*x^14-114240891994053278667816463617644163130982400*x^13+9426308681155313633978186680517583457222656000*x^12-667007205032432617042074106024090586358743040000*x^11+40262812208288613386756624451412873062602709663744*x^10-2058895657813724241497109079901507402908292119265280*x^9+88384296558915056469828488574011062808611158082191360*x^8-3147729759150235865486481167139605980761099627134976000*x^7+91574884244836006825731031456966517963624535941317656576*x^6-2131660368212322429000362223499574075024409810348099502080*x^5+38582585061921222023674796083363738509567642564605824204800*x^4-520846665582617300992960074377766135346358790329966002176000*x^3+4910528693639351019150216724989560358849367435427425812480000*x^2-28697113776054561256339177690399517111889564354055294156800000*x+77834900638717728810292956388807533535630325137671192575999999)+2443953593087009142735937776225158103864291124304498937941483520000*x^2-(1/2)*abs(x^30-4800*x^29+11024000*x^28-16128000000*x^27+16881863040000*x^26-13462944768000000*x^25+8504819980800000000*x^24-4368822681600000000000*x^23+1858904901744384000000000*x^22-664000202247782400000000000*x^21+201089035075848192000000000000*x^20-52008721052604825600000000000000*x^19+11548141599993995182080000000000000*x^18-2209345031158535946240000000000000000*x^17+364998498206293899018240000000000000000*x^16-52121154058892919963648000000000000000000*x^15+6431985687097659421664870400000000000000000*x^14-685013175795388287638568960000000000000000000*x^13+62802435693341373836558336000000000000000000000*x^12-4937678919944184606071193600000000000000000000000*x^11+331172233220931243960617559654400000000000000000000*x^10-18816621083376177150389303377920000000000000000000000*x^9+897511252240835825538816383385600000000000000000000000*x^8-35515646354006726917556168294400000000000000000000000000*x^7+1148037704985584815731551886114816000000000000000000000000*x^6-29693081813279953895342357033779200000000000000000000000000*x^5+597153630358013779850556635873280000000000000000000000000000*x^4-8956990907033466273274741653504000000000000000000000000000000*x^3+93829194664240113261728287948800000000000000000000000000000000*x^2-609263899579478525925780357120000000000000000000000000000000000*x+1836111675302430858465509375999999999999999999999999999999999999)+14*x^30-52080*x^29+117874120*x^28-16165073573623770523198782950086523615232000*x^15-(1/2)*abs(x^30-2880*x^29+3968640*x^28-3483648000*x^27+2187889449984*x^26-1046878585159680*x^25+396800881024204800*x^24-122299074619637760000*x^23+31222464154482952765440*x^22-6691592182191667701350400*x^21+1215908498656641012675379200*x^20-188686108842102518590734336000*x^19+25137790648493706418420847738880*x^18-2885557942773162398037766569984000*x^17+286028022082315767626690126571110400*x^16-24506584017263887368743437360693248000*x^15+1814533854648639454428718901559023370240*x^14-115949847418456110679897775251312449945600*x^13+6378212647686732276220883529930192715776000*x^12-300882274291249502401127911521098724802560000*x^11+12108181556052120548256322843623018945727954944*x^10-412779287924716495876066193778753806485967339520*x^9+11813196023754560945349227800828810974086729564160*x^8-280477793170426080487366288478860521099497570304000*x^7+5439840436993272973046981788125459146579000621531136*x^6-84418286844781638547591068024381308771458460072017920*x^5+1018634982551790282079773751056518875422146362657996800*x^4-9167393929263218455051678749551840032017234624774144000*x^3+57619966246286893153232409648329578034961389275054080000*x^2-224487264040624309822974745816103388425252330746675200000*x+405916405104110833327208685722723013386117396299775999999))

[gmalivuk]

The fact that there's a polynomial at the end doesn't mean the process of getting it can be done in polynomial time.

[Spacemoss]

That's true, and I'm not an expert on Time Complexity Spaces, actually I've only recently become more familiar with them. In fact, I've sought help for finding the exact complexity of this, and some of the other formulae I have, however, I've yet to get much assistance. In this case, most of the initial operations are in linear time with regards to the size of the input, simple multiplications and divisions, albeit of large numbers, and the fact that indexes need only run to the value of the input itself, seems to only move it in to x^2 complexity, that is, still polynomial time. Regardless, my amateur basic analysis indicates that it's on the order of x^2 or x^3, and I've seen no reason yet to suggest that is exponential or greater.

Moreover, and regardless of whether it is actually calculable in polynomial time, these functions provide long sought answers to the Exact Distribution of the Primes built into one function, not an algorithm, not an estimation, without brute forcing, (or that it has all the brute forcing built into a single function, depending on your perspective), in fact in a polynomial, no matter how awkward, as well the Exact number of factors of all numbers in one equation, as well as a way to show all individual factors, as well as the infamous equation for the n-th prime. Not to mention their are multiple options, once the technique is understood.

As such, they serve as building blocks to be refined, as I am certain the method can only improve over time, and with the assistance of others. I look forward to discussing these topics with the forum further, once the larger body of the work may be reviewed, and the forms become more apparent.

[gmalivuk]

If it takes around x steps to do something with input x, that's exponential in the *size* of the input.

Linear means a 100-digit input takes about twice as long as a 50-digit input. Polynomial time means it takes approximately some fixed higher power of 2. You seem to be talking about a process that will take 10^50 times longer.

[DavidSh]

I will point out that the presence of the absolute value function means that F() and H() are not actually polynomials as such.

[lightvector]

To clarify what gmalivuk said in case there's a misunderstanding of what "size" means - normally when people talk about complexity theory, they're talking about something's running time relative to the number of *bits* or *digits* in the input.

So if your algorithm takes 10 times longer for a number that is 10 times larger in numeric value, that means it takes 10 times longer as a result of adding 1 digit, so it is exponential in the number of digits, which is pretty bad compared to known ways of computing primes.

[Spacemoss]

Thanks again for the replies, and for clarifying. It seems you're saying it's a function of change in input rather than simply a function of input. Bits and Digits are different though, and I thought the complexity may also be dependent on the numerical base and the physical architecture of the system being used.

I posted in this thread because it started as a pattern for the primes thread, and that was the intention of my comment, to contribute a pattern. I tacked on the part about the complexity, as part of my own personal question and secondary and newer interest on the topic. I looked around and also posted something similar in a percentage of primes thread, but I don't really see a thread that covers the full scope of my material.

After this reply, and the similar one I will make on the other thread, I will make a proper thread, and include the material so anyone who wishes to discuss it may do so. It's much easier to convey concepts with visuals, pdfs, and formulae panels. If it turns out people feel it belongs in an existing thread, that's fine.

[Xanthir]

↶
Bits and Digits are different though,

They're not. Bits are just digits in base 2 vs base 10.

and I thought the complexity may also be dependent on the numerical base and the physical architecture of the system being used.

Numerical base dependencies almost never occur, and when they do, they're almost always extremely obvious, based on you literally twiddling numbers in the base-N representation of the value. I'm pretty certain you're not doing that here.

System architecture dependencies never matter unless you're (a) doing very low-level optimizations, where keeping a calculation in registers is important to shave nanoseconds off of a hot loop, or (b) are designing specialty algorithms that run more efficiently on a quantum computer or the like. You're not doing either - in particular, the second requires a good understanding of the differences in the sorts of algorithms that can run differently, or else you're virtually guaranteed to write something that actually falls back down to being equally slow/fast on both classic and quantum computers.

[gmalivuk]

When we talk about "polynomial time" or whatever, we're just counting the number of basic operations in a computation. That those basic operations may run faster on some machines doesn't affect how many there are, and changing base would at most change the number of basic operations by some constant multiplier, which we already ignore.