Oblong pandigital numbers

In this blogpost, I wrote about pandigital numbers (numbers in base n>1 that uses the numbers 0 to n-1 exactly once) that are also squares and a nice result of Adam Partridge that showed such square pandigital numbers do not exist if n is odd and n-1 has an even 2-adic valuation. A different approach to prove this result can be found in this article. It turns out that a similar result exists for oblong (or pronic) pandigital numbers.

Theorem: There are no oblong pandigital numbers in base n if n ≡ 3 (mod 4). 

Proof: Since nᵃ ≡ 1 (mod n-1), k ≡ m (mod n-1), where m is the digit sum of k in base n. Thus for a number k with every digit exactly once, k ≡ n(n-1)/2 (mod n-1).

Suppose n ≡ 3 (mod 4), i.e. n=2q+1 for some odd q. Then n(n-1)/2 = 2q²+q. Since n-1 = 2q, this means that n(n-1)/2 ≡ q (mod n-1). As q is odd, m(m+1) is even and n-1 is even, this implies that m(m+1) ≠ q (mod n-1) and thus m(m+1) is not a number with every digit exactly once and the proof is complete.

Conjecture: There are oblong pandigital numbers in base n if n !≡ 3 (mod 4).

Nearest integer with the same Hamming weight

Theorem: For a positive integer n, the nearest integer not equal to n with the same Hamming weight as n is larger than n if and only if n is odd.

Proof: If n is of the form 2ᵏ-1, then n is odd and there are no smaller positive integers with the same Hamming weight as n and the nearest integer not equal to n with the the same Hamming as n is equal to (3n+1)/2 > n.

Let us denote a(n) as the smallest integer > n with the same Hamming weight as n. For n not of the form 2ᵏ-1, let us denote b(n) as the largest integer < n with the same Hamming weight as n. Let us denote c(n) as the nearest integer not equal to n with the same Hamming weight as n.

If n is of the form (2ᵏ-1)*2ᵐ for some k, m>0, then n is even and in binary is of the form 11..1100..00 and a(n) = 2ᵏ⁺ᵐ+2ᵏ⁻¹-1, i.e. 100..0011..11 in binary. On the other hand, b(n) = (2ᵏ⁻¹-1)*2ᵐ⁺¹+2ᵐ⁻¹, i.e. 11..110100..00 in binary. Thus a(n)-n = 2ᵏ⁻¹-1+2ᵐ ≥ 2ᵐ and n-b(n) = 2ᵐ⁻¹ < 2ᵐ. Therefore c(n) = b(n).

If n is not of the form (2ᵏ-1)*2ᵐ, then n in binary is of the form xxx...xxx0yyy...yyy, where xxxxxx and yyyyy are both not all zeros. If yyy...yyy is of the form 2ʳ-1, then b(n) must flip one of the '1' bit in xxx...xxx whereas a(n) leaves xxx...xxx unchanged. Thus n-b(n) > a(n)-n. Otherwise a(n) and b(n) will not change the bits xxx...xxx and reduces to the problem for yyy...yyy and thus the result follows by induction.

In particular, this proof shows that c(n) = a(n) if n is odd and c(n) = b(n) if n is even. It also shows that a tie never occurs in determining c(n), i.e. a(n)-n is not equal to n-b(n) for all n>0.

In The On-Line Encyclopedia of Integer Sequences (OEIS), a(n) is given by sequence A057168, b(n) is given by A243109 and c(n) is given by A381764.