[seqfan] Finding terms for a(n) is the smallest number that has exactly n evil divisors (A001969).

David Corneth davidacorneth at gmail.com
Tue Jul 26 20:47:38 CEST 2022


Hi all,

So the sequence I'm referring (see title) is A356019. It's about the number
of evil divisors of some k. A number is evil if the number of ones in the
binary expansion is even (See A001969)
I'm looking to put a b-file for a(n) for n = 0..10000. For those values I
have upper bounds.
I find two strategies (or maybe three if you will) to find terms (not upper
bounds).
1. *Check all positive integers k (starting at 1 going up). Check how many
evil divisors k has. If that number of evil divisors is unseen (and <=
10000), store it as a new term. *
So I did that to 8*10^9 (some of you guys will have stronger machines or
better algorithms or more patience than me). But that got me the first 397
values of a(n) (for n = 0...396).
The first value I'm not sure of is a(397). My current upper bound is
10801115325.

To verify its precense in the sequence I could go back to strategy 1 or
maybe try another strategy, strategy 2.

2. *Look at A002182 (highly composite numbers, the actual one). Find the
least m > 1 such that A002182(m) > **10801115325. Thats m = 67. Look up
A002182(m-1). That's A002182(66) = **735134400. That number has 1344
divisors. So if some number < 10801115325 has exactly 397 evil divisors,
its number of divisors is in [397, 1344]. *
But we can maybe use some properties of the number of evil divisors of some
number. Which brings us to strategy 2*.
2*
*Compute the number of evil divisors of k via the odd divisors of k and the
2-adic value of k (cf. A007814) to find that a(397) must be odd.*
One could for example find the evil divisors of 40 by listing its divisors (1,
2, 4, 5, 8, 10, 20, 40) and checking each of them to see if its evil. But
evilness only depends on the number of ones in the binary expansion. So who
cares about the trailing zeros of divisors. We could just see the 2-adic
valuation of 40 (which is 3). The odd divisors of 40 are {1, 5}. Of those,
5 is evil. As the 2-adic valuation of 40 is 3, there are 3+1 = 4 divisors
of 40 of the form 5*2^j. Therefore, via 5 we find 4 evil divisors of 40.
More generally, let E(k) is the number of evil divisors of k. If k = m *
2^j where m is odd then E(m) = E(k*2^j) = E(k) * (j + 1).

*It turns out that a(397) is either 3*2^(397-1) or some odd number. Let k =
a(397) = m * 2^j where m is odd. *
*We have 397 = E(k) * (j + 1) so j+1 | 397 i.e. j + 1 = 1 or j + 1 = 397.*
*That gives to cases for the number of evil divisors of m. That number is
either 1 or 397. *
*So we maybe could use a sequence that lists the smallest k such that E(k)
= 2*n-1 for n>0 and use that to find a(n). *

Now for the upper bounds, I made a list of 59-smooth numbers and used the
good old A025487 (products of primorials) to find and tighten bounds. But
that doesn't prove terms.

One additional trick is to stop the calculation of the number of evil
divisors early.
6486480 has 400 divisors. Say we'd like to see if 397 of them are evil. If
we find 4 odious (=non-evil) divisors we're done. No need to look any
further.

So, any thoughts on how to proceed?

Best,
David



More information about the SeqFan mailing list