0
$\begingroup$

Function Problem: Given $N$ find a $2$_$sum$ that uses at least $ONE$ prime.

Fact: Prime Gaps grow logarithmically on average. And, in worst case if memory serves correct it grows with a bounded constant.

  • Take notice that $count$ (defined below) will only equal to $s$, if the $AKS$ primality statement executes $s$ times. This will find our $s$-amount primes to generate a $2$_$sum$ by finding the difference of $N$-$P$.

Algorithm

$N$ = $13$

$s$ = $binary~length~of~N$

$p$ = 0

$count$ = $0$

$primes$ = []

$WHILE$ $count$ $<$ $s$:

$~~~~~~~~~$ $p$=$p$+$1$

$~~~~~~~~~$ $IF$ $AKS$-$PRIMALITY$($p$) == $TRUE$:

$~~~~~~~~~~~~~~~~~~~$ $primes$.append($p$)

$~~~~~~~~~~~~~~~~~~~$ $count$ = $count$ + 1

$OUTPUT$ FOUND $2$_$SUM$, $(N-P)$ + $P$

$OUTPUT$ VERIFY SOLUTION $(N-P)$+$P$ == $N$

Found 2-sum:  6 + 7
Verify Solution:  True

I'm an amateur who made computer-science a hobby, and I'm not sure what would the exact time complexity would be.

Question

What would be the best estimate of the time complexity?

Would it fail if $P$ $>$ $N$? (an easy fix)

$\endgroup$
  • $\begingroup$ I can improve space complexity by getting rid of the appending and just using $primes$ = $p$ instead! I noticed a speedup in python by doing this! $\endgroup$ – Dingle Berry May 27 '20 at 2:09
  • 1
    $\begingroup$ What does the output have to do with $N$? What is a 2_Sum? What's wrong with $P=2$? $\endgroup$ – Yonatan N May 27 '20 at 6:32
  • $\begingroup$ @YonatanN That would be boring if we use fixed primes. And, I should've said that that a 2_sum is two integers added together that equals $N$. $\endgroup$ – Dingle Berry May 28 '20 at 0:35

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Browse other questions tagged or ask your own question.