This site is supported by donations to The OEIS Foundation.

# User:Daniel Suteu

Free and open-source software developer, with main interests in programming languages, algorithms, mathematics (number theory), poetry and anarchism.

In March 2013, I started the Sidef programming language project, which combines many good things from good languages, trying to make programming easier and more enjoyable, focusing primarily on simplicity, elegance and readability.

Among other things, the language comes with fast built-in methods for primality testing and prime factorization, along with many other number-theoretic functions, most of them provided by Dana Jacobsen's excellent Math::Prime::Util::GMP module. Also built-in, we have support for arbitrary large integers, rationals, floats and complex numbers, using the GMP, MPFR and MPC libraries.

The language can be tried online at: https://tio.run/#sidef.

WWW:

## Partial sums of arithmetical functions

For any arithmetical function ${\displaystyle f(k)}$, we have the following identity (for m >= 0):

${\displaystyle \sum _{k=1}^{n}\sum _{d|k}f(d)(k/d)^{m}=\sum _{k=1}^{n}f(k)\sum _{j=1}^{\left\lfloor n/k\right\rfloor }j^{m}=\sum _{k=1}^{n}f(k)F_{m}(\left\lfloor n/k\right\rfloor )}$

where ${\displaystyle F_{n}(x)}$ are the Faulhaber polynomials, defined as:

${\displaystyle F_{n}(x)={\frac {B_{n+1}(x+1)-B_{n+1}(1)}{n+1}}}$

where ${\displaystyle B_{n}(x)}$ are the Bernoulli polynomials. The Faulhaber polynomials are particularly useful in efficiently summing the m-th powers of the first n positive integers (with m >= 0):

${\displaystyle \sum _{k=1}^{n}k^{m}=F_{m}(n)}$

...and are also useful in efficiently computing second partial sums of m-th powers (sums of power sums) with m >= 0:

${\displaystyle \sum _{k=1}^{n}\sum _{j=1}^{k}j^{m}=(n+1)F_{m}(n)-F_{m+1}(n)}$

In this section, we're interested in computing the following partial sum in sublinear time, with m >= 0, where ${\displaystyle f(k)}$ is an arithmetical function:

${\displaystyle \sum _{k=1}^{n}f(k)F_{m}(\left\lfloor n/k\right\rfloor )}$

If the partial sums of ${\displaystyle f(k)}$ can be computed efficiently:

${\displaystyle S(n)=\sum _{k=1}^{n}f(k)}$

then it's possible to create the following sublinear formula:

${\displaystyle \sum _{k=1}^{n}f(k)F_{m}(\left\lfloor n/k\right\rfloor )=\sum _{k=1}^{\left\lfloor {\sqrt {n}}\right\rfloor }F_{m}(k)(S(\left\lfloor n/k\right\rfloor )-S(\left\lfloor n/(k+1)\right\rfloor ))+\sum _{k=1}^{\left\lfloor n/(\left\lfloor {\sqrt {n}}\right\rfloor +1)\right\rfloor }f(k)F_{m}(\left\lfloor n/k\right\rfloor )}$

More generally, the partial sums over the Dirichlet convolution of two arithmetic functions ${\displaystyle f}$ and ${\displaystyle g}$, can be computed in sublinear time, if the individual partial sums of ${\displaystyle f}$ and ${\displaystyle g}$ can be computed efficiently:

${\displaystyle R(n)=\sum _{k=1}^{n}f(k)}$

${\displaystyle S(n)=\sum _{k=1}^{n}g(k)}$

Assuming that ${\displaystyle R(n)}$ and ${\displaystyle S(n)}$ can be computed efficiently, then we can use the Dirichlet hyperbola method to compute the following partial sum in sublinear time:

${\displaystyle \sum _{k=1}^{n}\sum _{d|k}f(d)g(k/d)=\sum _{k=1}^{\left\lfloor {\sqrt {n}}\right\rfloor }(f(k)S(\left\lfloor n/k\right\rfloor )+g(k)R(\left\lfloor n/k\right\rfloor ))-R(\left\lfloor {\sqrt {n}}\right\rfloor )S(\left\lfloor {\sqrt {n}}\right\rfloor )}$

## Partial sums of the sigma function

For m >= 0 and j >= 0, we have:

${\displaystyle \sum _{k=1}^{n}k^{m}\sigma _{j}(k)=\sum _{k=1}^{n}k^{m+j}F_{m}(\left\lfloor n/k\right\rfloor )=\sum _{k=1}^{n}k^{m}F_{m+j}(\left\lfloor n/k\right\rfloor )}$

which can be computed in sublinear time by using the Dirichlet hyperbola method:

${\displaystyle \sum _{k=1}^{n}k^{m}\sigma _{j}(k)=\sum _{k=1}^{\lfloor {\sqrt {n}}\rfloor }(k^{m}F_{m+j}(\left\lfloor n/k\right\rfloor )+k^{m+j}F_{m}(\left\lfloor n/k\right\rfloor ))-F_{m+j}(\left\lfloor {\sqrt {n}}\right\rfloor )F_{m}(\left\lfloor {\sqrt {n}}\right\rfloor )}$

where ${\displaystyle F_{n}(x)}$ are the Faulhaber polynomials.

An asymptotic approximation to this partial sum, with m >= 0 and j >= 1, is given by the following formula:

${\displaystyle \sum _{k=1}^{n}k^{m}\sigma _{j}(k)\sim {\frac {\zeta (j+1)n^{j+m+1}}{j+m+1}}}$

where ${\displaystyle \zeta (s)}$ is the Riemann zeta function.

## Partial sums of the Jordan totient function

The Jordan totient function is a generalization of the Euler totient function, and is defined as:

${\displaystyle J_{m}(n)=n^{m}\prod _{p|n}(1-1/p^{m})}$

and is multiplicative with:

${\displaystyle J_{m}(p^{k})=p^{km}-p^{(k-1)m}}$

An elegant formula for computing partial sums of the Jordan totient function, is given in terms of the Möbius function and the Faulhaber polynomials:

${\displaystyle \sum _{k=1}^{n}J_{m}(k)=\sum _{k=1}^{n}\mu (k)F_{m}(\left\lfloor n/k\right\rfloor )}$

An asymptotic approximation to this partial sum, with m >= 1, is given by:

${\displaystyle \sum _{k=1}^{n}J_{m}(k)\sim {\frac {n^{m+1}}{(m+1)\zeta (m+1)}}}$

where ${\displaystyle \zeta (s)}$ is the Riemann zeta function.

## Partial sums of the Dedekind psi function

The generalized Dedekind psi function can be defined in terms of the Jordan totient function, as:

${\displaystyle \psi _{m}(n)={\frac {J_{2m}(n)}{J_{m}(n)}}}$

and is multiplicative with:

${\displaystyle \psi _{m}(p^{k})=p^{km}+p^{(k-1)m}}$

Partial sums of the Dedekind psi function can be expressed in terms of the absolute value of the Möbius function and the Faulhaber polynomials:

${\displaystyle \sum _{k=1}^{n}\psi _{m}(k)=\sum _{k=1}^{n}|\mu (k)|F_{m}(\left\lfloor n/k\right\rfloor )}$

with the following asymptotic approximation for m >= 1:

${\displaystyle \sum _{k=1}^{n}\psi _{m}(k)\sim {\frac {n^{m+1}\zeta (m+1)}{(m+1)\zeta (2(m+1))}}}$

where ${\displaystyle \zeta (s)}$ is the Riemann zeta function.

## Partial sums of the omega(n) and bigomega(n) functions

We define the generalized ${\displaystyle \omega _{m}(n)}$ and ${\displaystyle \Omega _{m}(n)}$ functions as:

${\displaystyle \omega _{m}(n)=\sum _{p^{k}|n}{\frac {n^{m}}{p^{m}}}}$

${\displaystyle \Omega _{m}(n)=\sum _{p^{k}|n}\sum _{j=1}^{k}{\frac {n^{m}}{p^{jm}}}}$

where ${\displaystyle p^{k}}$ are primes ${\displaystyle p}$ dividing ${\displaystyle n}$, with multiplicity ${\displaystyle k}$.

For ${\displaystyle \omega _{m}(n)}$ we have the following sequences:

${\displaystyle \omega _{0}(n)=}$ A001221(n)

${\displaystyle \omega _{1}(n)=}$ A069359(n)

${\displaystyle \omega _{2}(n)=}$ A322078(n)

Similarly, for ${\displaystyle \Omega _{m}(n)}$, we have:

${\displaystyle \Omega _{0}(n)=}$ A001222(n)

${\displaystyle \Omega _{1}(n)=}$ A095112(n)

${\displaystyle \Omega _{2}(n)=}$ A322664(n)

Partial sums of this functions can be expressed in terms of the Faulhaber polynomials, as:

${\displaystyle \sum _{k=1}^{n}\omega _{m}(k)=\sum _{p}^{n}F_{m}(\left\lfloor n/p\right\rfloor )}$

${\displaystyle \sum _{k=1}^{n}\Omega _{m}(k)=\sum _{p^{k}}^{n}F_{m}(\left\lfloor n/p^{k}\right\rfloor )}$

where ${\displaystyle p}$ and ${\displaystyle p^{k}}$ (with k>=1) run over the prime numbers and the prime powers, respectively, less than or equal to ${\displaystyle n}$.

For m>=1, the partial sums of ${\displaystyle \omega _{m}(k)}$ can be described asymptotically as:

${\displaystyle \sum _{k=1}^{n}\omega _{m}(k)\sim F_{m}(n)P(m+1)}$

where ${\displaystyle F_{m}(n)}$ are the Faulhaber polynomials and ${\displaystyle P(s)}$ is the Prime zeta function, defined as:

${\displaystyle P(s)=\sum _{p}{\frac {1}{p^{s}}}}$

Very similarly, for m>=1, the partial sums of ${\displaystyle \Omega _{m}(k)}$ satisfy:

${\displaystyle \sum _{k=1}^{n}\Omega _{m}(k)\sim F_{m}(n)Q(m+1)}$

where ${\displaystyle F_{m}(n)}$ are the Faulhaber polynomials and ${\displaystyle Q(s)}$ is defined as:

${\displaystyle Q(s)=\sum _{k=1}^{\infty }\sum _{p}{\frac {1}{p^{sk}}}=\sum _{p}{\frac {1}{p^{s}-1}}}$

where ${\displaystyle p}$ runs over the prime numbers.

## Partial sums - OEIS sequences

Considering the following partial sum, where ${\displaystyle f(k)}$ is an arithmetic function and ${\displaystyle F_{n}(x)}$ are the Faulhaber polynomials:

${\displaystyle R_{m}(n)=\sum _{k=1}^{n}\sum _{d|k}f(d)(k/d)^{m}=\sum _{k=1}^{n}f(k)F_{m}(\left\lfloor n/k\right\rfloor )}$

gives us the following table of interesting sequences:

+------------+------------+------------+
|    f(k)    |   R_0(n)   |   R_1(n)   |
+------------+------------+------------+
| A000012(k) | A006218(n) | A024916(n) |
| A000027(k) | A024916(n) | A143127(n) |
| A010051(k) | A013939(n) | A322068(n) |
| A069513(k) | A022559(n) | A328893(n) |
| A008966(k) | A064608(n) | A173290(n) |
| A008683(k) | A000012(n) | A002088(n) |
| A000290(k) | A064602(n) | A143128(n) |
| A000010(k) | A000217(n) | A272718(n) |
| A034444(k) | A061503(n) | A306775(n) |
| A007434(k) | A000330(n) |            |
+------------+------------+------------+


## Generalized Pillai arithmetical function

For any arithmetical function ${\displaystyle f(k)}$, we have the following identity:

${\displaystyle \sum _{k=1}^{n}f(gcd(n,k))=\sum _{d|n}f(d)\phi (n/d)}$

where ${\displaystyle \phi (x)}$ is the Euler totient function.

## Abundant Fermat pseudoprimes

On 17 December 2017, Shyam Sunder Gupta published the following problem on their website: "Can you find the smallest abundant number which is also pseudoprime (base-2)?".

On 9th November 2019, I generated 42 abundant Fermat pseudoprimes to base 2, the smallest one in my list being the following 40-digit number:

${\displaystyle 3470207934739664512679701940114447720865}$

Meanwhile, I generated a few more abundant pseudoprimes to base 2, which can be found here.

Update (28 August 2022): using a new idea, I generated two smaller abundant Fermat pseudoprimes to base 2:

${\displaystyle 2596282479202818734176082185090403265}$

${\displaystyle 12796625128232187655293894634808130945}$

Challenge: find a smaller abundant Fermat pseudoprime to base 2, or prove that the above number is the smallest one.

## Abundant Carmichael numbers

Inspired by Shyam Sunder Gupta's problem, in A329460, Amiram Eldar asked the question: "Do abundant Carmichael numbers exist?".

On 15th August 2020, I answered the question in positive (source code) by generating the following 97-digit abundant Carmichael number, showing that abundant Carmichael numbers do exist:

${\displaystyle 2050222770372550554323267720953963601363820698627252818938445687085323309254089582862054255135745}$

In constructing abundant Carmichael numbers, one important idea (source code) is the following: if a Carmichael number is a multiple of an odd abundant cyclic number, such as:

${\displaystyle 8177568910636879136524885826320973235}$

or

${\displaystyle 17277031840122951876810012573270045985}$

then it will be abundant. Since the above multipliers are both odd abundant cyclic numbers and all odd cyclic numbers seem to have Carmichael multiples, suggests that infinitely many abundant Carmichael numbers do exist.

A day later, I constructed a slightly smaller (88-digit) abundant Carmichael number (but, most likely, it's still not the smallest one):

${\displaystyle 2059832906607460252767290568443059994787898033540634712711845135488141590979778401392385}$

Challenge: find an abundant Carmichael number divisible by 3.

Open problem: find the smallest abundant Carmichael number.

A list of Carmichael numbers with abundancy index > 1.9 can be found here.

## Abundant Lucas-Carmichael numbers

A related question would be: "do abundant Lucas-Carmichael numbers exist?". The answer is "yes"!

For generating abundant Lucas-Carmichael numbers, we used a similar method as in the generation of abundant Carmichael numbers.

First, we generated odd squarefree (almost) abundant numbers ${\displaystyle k}$ (source code), satisfying ${\displaystyle gcd(k,\psi (k))=1}$, where ${\displaystyle \psi (n)}$ is the Dedekind psi function. Such a number ${\displaystyle k}$ must be a term of A255602.

Then we used a modified version of Erdős's construction method for Carmichael numbers, adapted to the construction of Lucas-Carmichael numbers (source code) and also with support for using our multiplier ${\displaystyle k}$ with its corresponding lambda value ${\displaystyle L}$.

The smallest abundant Lucas-Carmichael number that I was able to find so far, is the following 70-digit number:

${\displaystyle 1012591408428327888883952080728349448745451794025524955777432246705535}$

It is conjectured that every term of A255602 is a divisor of a Lucas-Carmichael number. The smallest such multiples are given in A253598. If the conjecture is true, then there exists infinitely many abundant Lucas-Carmichael numbers, as the A255602 sequence includes infinitely many abundant terms.

Challenge: find an abundant Lucas-Carmichael number divisible by 3.

Open problem: find the smallest abundant Lucas-Carmichael number.

Several upper-bounds to A253598 are listed here.

A list of Lucas-Carmichael numbers with abundancy index > 1.9 is available here.

## Agrawal's conjecture

In the article Remarks on Agrawal's conjecture, Hendrick Lenstra showed that if a Carmichael number, with an odd number of prime factors ${\displaystyle p|n=>p=3\mod 80}$, is also a Lucas-Carmichael number, then it would be a counter-example to Agrawal's conjecture (cf. A329223).

Currently, only the following such Carmichael numbers are known, but none of them is also a Lucas-Carmichael number:

${\displaystyle 330468624532072027=2003*574003*287432003}$

${\displaystyle 1358406397003392026912594827=47051443*3811166803*7575282163}$

${\displaystyle 194462892367341977828363075381947=1571719603*22527980963*5492112195923}$

More Fermat pseudoprimes to base 2 with these properties, can be found here.

## Upper-bounds to some OEIS sequences

### Smallest anti-Carmichael Fermat psp-2 with ${\displaystyle n}$ prime factors

Thomas Ordowski defined the following interesting sequence: ${\displaystyle a(n)=}$ A316908${\displaystyle (n)}$ is the smallest ${\displaystyle k}$ with ${\displaystyle n}$ prime factors such that ${\displaystyle 2^{k-1}=1\mod k}$ and ${\displaystyle p-1}$ does not divide ${\displaystyle k-1}$ for every prime ${\displaystyle p}$ dividing ${\displaystyle k}$.

${\displaystyle a(9)<=797365221484475174021}$

${\displaystyle a(10)<=1315856103949347820015303981}$

${\displaystyle a(11)<=6357507186189933506573017225316941}$

${\displaystyle a(12)<=77822245466150976053960303855104674781}$

${\displaystyle a(13)<=42864570625001423761497389323695509974049581}$

${\displaystyle a(14)<=34015651529746754841597629769101132590516759547941}$

${\displaystyle a(15)<=53986954871543199290951271756765558658193549930487667861}$

More upper-bounds can be found here.

### Smallest imprimitive Carmichael number with ${\displaystyle n}$ prime factors

Amiram Eldar defined the following interesting sequence: ${\displaystyle a(n)=}$ A328938${\displaystyle (n)}$ is the smallest imprimitive Carmichael number with ${\displaystyle n}$ prime factors.

An imprimitive Carmichael number is defined to be a Carmichael number, ${\displaystyle n=p_{1}*p_{2}*...*p_{k}}$, such that:

${\displaystyle gcd(p_{1}-1,p_{2}-1,...,p_{k}-1)^{2}>lcm(p_{1}-1,p_{2}-1,...,p_{k}-1)}$

The list of imprimitive Carmichael numbers is given by A328935.

${\displaystyle a(8)<=1717329690048308373193368241}$

${\displaystyle a(9)<=3267914929260691848833226795711841}$

${\displaystyle a(10)<=16412975107923138847512341751620644377601}$

${\displaystyle a(11)<=325533792014488126487416882038879701391121}$

${\displaystyle a(12)<=1605045791181700950034233564955898780122791301414374937801}$

${\displaystyle a(13)<=1802188215375086135161896807172372148518756613537876342449815601}$

${\displaystyle a(14)<=37301957856686414877340399600312307212530668530569712518803959550606029812859921}$

${\displaystyle a(15)<=111752741147928878460543122185614013584493764844954493341714777557828905006762368931787841}$

More upper-bounds can be found here.

### Smallest super-pseudoprime to base 2 with ${\displaystyle n}$ prime factors

Also submitted by Amiram Eldar, the sequence ${\displaystyle a(n)=}$ A328665${\displaystyle (n)}$ lists the smallest super-pseudoprime to base 2 with ${\displaystyle n}$ prime factors.

The list of super-pseudoprimes to base 2 is given by A050217.

${\displaystyle a(7)<=1842158622953082708177091}$

${\displaystyle a(8)<=192463418472849397730107809253922101}$

${\displaystyle a(9)<=1347320741392600160214289343906212762456021}$

${\displaystyle a(10)<=70865138168006643427403953978871929070133095474701}$

${\displaystyle a(11)<=3363391752747838578311772729701478698952546288306688208857}$

${\displaystyle a(12)<=132153369641266990823936945628293401491197666138621036175881960329}$

${\displaystyle a(13)<=9105096650335639994239038954861714246150666715328403635257215036295306537}$

${\displaystyle a(14)<=7605797846771738682631804190686245080923244102451432651379391224410677241944951032625821}$

More upper-bounds can be found here.

### Smallest super-pseudoprime to base 2 Carmichael number with ${\displaystyle n}$ prime factors

In 2017, Max Alekseyev and Thomas Ordowski submitted the A291637 sequence, which lists the Carmichael numbers that are also super-pseudoprimes to base ${\displaystyle 2}$.

Letting ${\displaystyle a(n)}$ to be the smallest such number with n prime factors, we have:

${\displaystyle a(3)=294409}$

${\displaystyle a(4)=3018694485093841}$

By using the tables of pseudoprimes up to ${\displaystyle 2^{64}}$, we find that ${\displaystyle a(5)>2^{64}}$.

${\displaystyle a(5)<=521635331852681575100906881}$

${\displaystyle a(6)<=2835402730651853232634509813787097410561}$

${\displaystyle a(7)<=165784025660216242122027716057592895796242004385542265601}$

A list of terms with ${\displaystyle 5}$ or more prime factors, can be found here.

### Smallest overpseudoprime to base 2 Carmichael number with ${\displaystyle n}$ prime factors

The sequence A352987 lists the Carmichael numbers that are also overpseudoprimes to base 2.

Letting ${\displaystyle a(n)}$ to be the smallest such number with n prime factors, we have:

${\displaystyle a(3)=65700513721}$

${\displaystyle a(4)<=84286331493236478328609}$

${\displaystyle a(5)<=3157343757823970959759947380425728583752001}$

A list of terms with ${\displaystyle 4}$ or more prime factors, can be found here

### Smallest overpseudoprime to base 2 with ${\displaystyle n}$ prime factors

Inspired by the A328665 sequence, in A353409 we list the smallest overpseudoprime to base 2 with ${\displaystyle n}$ distinct prime factors.

Some upper-bounds to this sequence are:

${\displaystyle a(5)<=1376414970248942474729}$

${\displaystyle a(6)<=48663264978548104646392577273}$

${\displaystyle a(7)<=294413417279041274238472403168164964689}$

${\displaystyle a(8)<=98117433931341406381352476618801951316878459720486433149}$

${\displaystyle a(9)<=1252977736815195675988249271013258909221812482895905512953752551821}$

More upper-bounds can be found here.