J. Sorenson

activity

20092020

most citedStrong Pseudoprimes to Twelve Prime Bases

16 citations · 43 across the 10 of their papers we have counts for

collaborators

10 papers

math.NT2020

Algorithms to Uniformly Generate Random Factored Smooth Integers

Eric Bach, Jonathan Sorenson

Let $x \geq y > 0$ be integers. A positive integer is $y$ -smooth if all its prime divisors are at most $y$ . Let $Ψ (x, y)$ count the number of $y$ -smooth integers up to $x$ . We present s…

math.NT2019

An Algorithm and Estimates for the Erdős-Selfridge Function (work in progress)

Brianna Sorenson, Jonathan P Sorenson, Jonathan Webster

Let $p (n)$ denote the smallest prime divisor of the integer $n$ . Define the function $g (k)$ to be the smallest integer $> k + 1$ such that $p ((k g ( k ))) > k$ . So we have $g (2) = 6$ …

math.NT2018★ 4 cited

Two Algorithms to Find Primes in Patterns

Jonathan P. Sorenson, Jonathan Webster

Let $k \geq 1$ be an integer, and let $P = (f_{1} (x), \dots, f_{k} (x))$ be $k$ admissible linear polynomials over the integers, or \textit{the pattern}. We present two algorithms that f…

math.NT2015★ 16 cited

Strong Pseudoprimes to Twelve Prime Bases

Jonathan P. Sorenson, Jonathan Webster

Let $ψ_{m}$ be the smallest strong pseudoprime to the first $m$ prime bases. This value is known for $1 \leq m \leq 11$ . We extend this by finding $ψ_{12}$ and $ψ_{13}$ . We also pres…

cs.DS2015★ 7 cited

Two Compact Incremental Prime Sieves

Jonathan P. Sorenson

A prime sieve is an algorithm that finds the primes up to a bound $n$ . We say that a prime sieve is incremental, if it can quickly determine if $n + 1$ is prime after having found al…

cs.DS2013★ 2 cited

Approximately counting semismooth integers

Eric Bach, Jonathan Sorenson

An integer $n$ is $(y, z)$ -semismooth if $n = p m$ where $m$ is an integer with all prime divisors $\leq y$ and $p$ is 1 or a prime $\leq z$ . arge quantities of semismooth integers are u…

cs.DS2012★ 7 cited

Near-Optimal Online Multiselection in Internal and External Memory

Jérémy Barbay, Ankur Gupta, S. Srinivasa Rao +1

We introduce an online version of the multiselection problem, in which q selection queries are requested on an unsorted array of n elements. We provide the first online algorithm t…

math.NT2010★ 4 cited

Sieving for pseudosquares and pseudocubes in parallel using doubly-focused enumeration and wheel datastructures

Jonathan P. Sorenson

We extend the known tables of pseudosquares and pseudocubes, discuss the implications of these new data on the conjectured distribution of pseudosquares and pseudocubes, and presen…

cs.DS2009

Online Sorting via Searching and Selection

Ankur Gupta, Anna Kispert, Jonathan P. Sorenson

In this paper, we present a framework based on a simple data structure and parameterized algorithms for the problems of finding items in an unsorted list of linearly ordered items…

cs.DS2009★ 3 cited

A Randomized Sublinear Time Parallel GCD Algorithm for the EREW PRAM

Jonathan P. Sorenson

We present a randomized parallel algorithm that computes the greatest common divisor of two integers of n bits in length with probability 1-o(1) that takes O(n loglog n / log n) ex…