Dudeney number explained

is a natural number equal to the perfect cube of another natural number such that the digit sum of the first natural number is equal to the second. The name derives from Henry Dudeney, who noted the existence of these numbers in one of his puzzles, Root Extraction, where a professor in retirement at Colney Hatch postulates this as a general method for root extraction.

Mathematical definition

Let

be a natural number. We define the Dudeney function for base

b>1

and power

p>0

F_p,:N → N

to be the following:

F_p,(n)=

	k-1
\sum
	i=0

	n^p\bmod{bⁱ⁺¹
	-

n^p\bmodb^i}{b^i}

where

k=p\left(\lfloorlog_b{n}\rfloor+1\right)

is the

times the number of digits in the number in base

A natural number

is a Dudeney root if it is a fixed point for

F_p,

, which occurs if

F_p,(n)=n

. The natural number

m=n^p

is a generalised Dudeney number,^[1] and for

p=3

, the numbers are known as Dudeney numbers.

and

are trivial Dudeney numbers for all

and

, all other trivial Dudeney numbers are nontrivial trivial Dudeney numbers.

For

p=3

and

b=10

, there are exactly six such integers :

1,512,4913,5832,17576,19683

A natural number

is a sociable Dudeney root if it is a periodic point for

F_p,

, where

	k(n)
F
	p,b

for a positive integer

, and forms a cycle of period

. A Dudeney root is a sociable Dudeney root with

k=1

, and a amicable Dudeney root is a sociable Dudeney root with

k=2

. Sociable Dudeney numbers and amicable Dudeney numbers are the powers of their respective roots.

The number of iterations

needed for

	i
F
	p,b

(n)

to reach a fixed point is the Dudeney function's persistence of

, and undefined if it never reaches a fixed point.

It can be shown that given a number base

and power

, the maximum Dudeney root has to satisfy this bound:

n\leq(b-1)(1+p+log_b{n^p})=(b-1)(1+p+plog_b{n}))

implying a finite number of Dudeney roots and Dudeney numbers for each order

and base

.^[2]

F_1,

is the digit sum. The only Dudeney numbers are the single-digit numbers in base

, and there are no periodic points with prime period greater than 1.

Dudeney numbers, roots, and cycles of F_p,b for specific p and b

All numbers are represented in base

p	b	Nontrivial Dudeney roots n	Nontrivial Dudeney numbers m=n^p	Cycles of F_p,(n)	Amicable/Sociable Dudeney numbers
2		\varnothing	\varnothing	\varnothing	\varnothing
2		2	11	\varnothing	\varnothing
2		3	21	\varnothing	\varnothing
2		4	31	\varnothing	\varnothing
2		5	41	\varnothing	\varnothing
2	7	3, 4, 6	12, 22, 51	\varnothing	\varnothing
2		7	61	2 → 4 → 2	4 → 20 → 4
2		8	71	\varnothing	\varnothing
2		9	81	13 → 16 → 13	169 → 256 → 169
2	11	5, 6, A	23, 33, 91	\varnothing	\varnothing
2		B	A1	9 → 13 → 14 → 12	69 → 169 → 194 → 144
2	13	4, 9, C, 13	13, 63, B1, 1E6	\varnothing	\varnothing
2	14	D	C1	9 → 12 → 9	5B → 144 → 5B
2	15	7, 8, E, 16	34, 44, D1, 169	2 → 4 → 2 9 → B → 9	4 → 11 → 4 56 → 81 → 56
2		6, A, F	24, 64, E1	\varnothing	\varnothing
3	2	\varnothing	\varnothing	\varnothing	\varnothing
3	3	11, 22	2101, 200222	12 → 21 → 12	11122 → 110201 → 11122
3	4	2, 12, 13, 21, 22	20, 3120, 11113, 23121, 33220	\varnothing	\varnothing
3	5	3, 13, 14, 22, 23	102, 4022, 10404, 23403, 32242	12 → 21 → 12	2333 → 20311 → 2333
3	6	13, 15, 23, 24	3213, 10055, 23343, 30544	11 → 12 → 11	1331 → 2212 → 1331
3	7	2, 4, 11, 12, 14, 15, 21, 22	11, 121, 1331, 2061, 3611, 5016, 12561, 14641	25 → 34 → 25	25666 → 63361 → 25666
3	8	6, 15, 16	330, 4225, 5270	17 → 26 → 17	6457 → 24630 → 6457
3	9	3, 7, 16, 17, 25	30, 421, 4560, 5551, 17618	5 → 14 → 5 12 → 21 → 12 18 → 27 → 18	148 → 3011 → 148 1738 → 6859 → 1738 6658 → 15625 → 6658
3	10	8, 17, 18, 26, 27	512, 4913, 5832, 17576, 19683	19 → 28 → 19	6859 → 21952 → 6859
3	11	5, 9, 13, 15, 18, 22	104, 603, 2075, 3094, 5176, A428	8 → 11 → 8 A → 19 → A 14 → 23 → 14 16 → 21 → 16	426 → 1331 → 426 82A → 6013 → 82A 2599 → 10815 → 2599 3767 → 12167 → 3767
3	12	19, 1A, 1B, 28, 29, 2A	5439, 61B4, 705B, 16B68, 18969, 1A8B4	8 → 15 → 16 → 11 → 8 13 → 18 → 21 → 14 → 13	368 → 2A15 → 3460 → 1331 → 368 1B53 → 4768 → 9061 → 2454 → 1B53
4	2	11, 101	1010001, 1001110001	\varnothing	\varnothing
4	3	11	100111	22 → 101 → 22	12121201 → 111201101 → 12121201
4	4	3, 13, 21, 31	1101, 211201, 1212201, 12332101	\varnothing	\varnothing
4	5	4, 14, 22, 23, 31	2011, 202221, 1130421, 1403221, 4044121	\varnothing	\varnothing
4	6	24, 32, 42	1223224, 3232424, 13443344	14 → 23 → 14	114144 → 1030213 → 114144
5	2	110, 111, 1001	1111001100000, 100000110100111, 1110011010101001	\varnothing	\varnothing
5	3	101	12002011201	22 → 121 → 112 → 110 → 22	1122221122 → 1222021101011 → 1000022202102 → 110122100000 → 1122221122
5	4	2, 22	200, 120122200	21 → 33 → 102 → 30 → 21	32122221 → 2321121033 → 13031110200 → 330300000 → 32122221
6	2	110	1011011001000000	111 → 1001 → 1010 → 111	11100101110010001 → 10000001101111110001 → 11110100001001000000 → 11100101110010001
6	3	\varnothing	\varnothing	101 → 112 → 121 → 101	1212210202001 → 112011112120201 → 1011120101000101 → 1212210202001

Extension to negative integers

Dudeney numbers can be extended to the negative integers by use of a signed-digit representation to represent each integer.

Programming example

The example below implements the Dudeney function described in the definition above to search for Dudeney roots, numbers and cycles in Python.def dudeneyf(x: int, p: int, b: int) -> int: """Dudeney function.""" y = pow(x, p) total = 0 while y > 0: total = total + y % b y = y // b return total

def dudeneyf_cycle(x: int, p: int, b: int) -> List: seen = [] while x not in seen: seen.append(x) x = dudeneyf(x, p, b) cycle = [] while x not in cycle: cycle.append(x) x = dudeneyf(x, p, b) return cycle

References

H. E. Dudeney, 536 Puzzles & Curious Problems, Souvenir Press, London, 1968, p 36, #120.

External links

Notes and References

Web site: Generalized Dudeney Numbers.
Web site: Rebol : Proving There are Only Six Dudeney Numbers.