Casting out nines

Casting out nines is a draft programming task. It is not yet considered ready to be promoted as a complete task, for reasons that should be found in its talk page.

A task in three parts:

Part 1

Write a procedure (say co9(x)) which implements Casting Out Nines as described by returning the checksum for x. Demonstrate the procedure using the examples given there, or others you may consider lucky.

Part 2

Notwithstanding past Intel microcode errors, checking computer calculations like this would not be sensible. To find a computer use for your procedure:

Consider the statement "318682 is 101558 + 217124 and squared is 101558217124" (see: Kaprekar numbers#Casting Out Nines (fast)).

note that 318682 has the same checksum as (101558 + 217124);

note that 101558217124 has the same checksum as (101558 + 217124) because for a Kaprekar they are made up of the same digits (sometimes with extra zeroes);

note that this implies that for Kaprekar numbers the checksum of k equals the checksum of k².

Demonstrate that your procedure can be used to generate or filter a range of numbers with the property co9(k) = co9(k²) and show that this subset is a small proportion of the range and contains all the Kaprekar in the range.

Part 3

Considering this Mathworld page, produce a efficient algorithmn based on the more mathmatical treatment of Casting Out Nines, and realizing:

co9(x) is the residual of x mod 9;

the procedure can be extended to bases other than 9.

Demonstrate your algorithm by generating or filtering a range of numbers with the property k%(Base − 1) = = (k²)%(Base − 1) and show that this subset is a small proportion of the range and contains all the Kaprekar in the range.

C++

Filter

 
// Casting Out Nines
//
// Nigel Galloway. June 24th., 2012
//
#include <iostream>
int main() {
	int Base = 10;
	const int N = 2;
	int c1 = 0;
	int c2 = 0;
	for (int k=1; k<pow((double)Base,N); k++){
		c1++;
		if (k%(Base-1) == (k*k)%(Base-1)){
			c2++;
			std::cout << k << " ";
		}
	}
	std::cout << "\nTrying " << c2 << " numbers instead of " << c1 << " numbers saves " << 100 - ((double)c2/c1)*100 << "%" <<std::endl;
	return 0;
}

Produces:

1 9 10 18 19 27 28 36 37 45 46 54 55 63 64 72 73 81 82 90 91 99
Trying 22 numbers instead of 99 numbers saves 77.7778%

The kaprekar numbers in this range 1 9 45 55 and 99 are included.

Changing: "int Base = 16;" Produces:

1 6 10 15 16 21 25 30 31 36 40 45 46 51 55 60 61 66 70 75 76 81 85 90 91 96 100
105 106 111 115 120 121 126 130 135 136 141 145 150 151 156 160 165 166 171 175
180 181 186 190 195 196 201 205 210 211 216 220 225 226 231 235 240 241 246 250
255
Trying 68 numbers instead of 255 numbers saves 73.3333%

The kaprekar numbers:

1 is 1

6 is 6

a is 10

f is 15

33 is 51

55 is 85

5b is 91

78 is 120

88 is 136

ab is 171

cd is 205

ff is 255

in this range are included.

Changing: "int Base = 17;" Produces:

1 16 17 32 33 48 49 64 65 80 81 96 97 112 113 128 129 144 145 160 161 176 177 19
2 193 208 209 224 225 240 241 256 257 272 273 288
Trying 36 numbers instead of 288 numbers saves 87.5%

The kaprekar numbers:

1 is 1

g is 16

3d is 64

d4 is 225

gg is 288

in this range are included.

C++11 For Each Generator

// Casting Out Nines Generator - Compiles with gcc4.6, MSVC 11, and CLang3
//
// Nigel Galloway. June 24th., 2012
//
#include <iostream>
#include <vector>
struct ran {
	const int base;
	std::vector<int> rs;
	ran(const int base) : base(base) { for (int nz=0; nz<base-1; nz++) if(nz*(nz-1)%(base-1) == 0) rs.push_back(nz); }
};
class co9 {
private:
	const ran* _ran;
	const int _end;
	int _r,_x,_next;
public:
	bool operator!=(const co9& other) const {return operator*() <= _end;}
	co9 begin() const {return *this;}
        co9 end() const {return *this;}
	int operator*() const {return _next;}
	co9(const int start, const int end, const ran* r)
	:_ran(r)
	,_end(end)
	,_r(1)
	,_x(start/_ran->base)
	,_next((_ran->base-1)*_x + _ran->rs[_r])
	{
		while (operator*() < start) operator++();
	}
	const co9& operator++() {
		const int oldr = _r;
		_r = ++_r%_ran->rs.size();
		if (_r<oldr) _x++;
		_next = (_ran->base-1)*_x + _ran->rs[_r];
		return *this;
	}
};
 
int main() {
	ran r(10);
	for (int i : co9(1,99,&r)) { std::cout << i << ' '; }
	return 0;
}

Produces:

1 9 10 18 19 27 28 36 37 45 46 54 55 63 64 72 73 81 82 90 91 99 

An alternative implementation for struct ran using http://rosettacode.org/wiki/Sum_digits_of_an_integer#C.2B.2B which produces the same result is:

 
struct ran {
	const int base;
	std::vector<int> rs;
	ran(const int base) : base(base) { for (int nz=0; nz<base-1; nz++) if(SumDigits(nz) == SumDigits(nz*nz)) rs.push_back(nz); }
};
 

Changing main:

int main() {
	ran r(16);
	for (int i : co9(1,255,&r)) { std::cout << i << ' '; }
	return 0;
}

Produces:

1 6 10 15 16 21 25 30 31 36 40 45 46 51 55 60 61 66 70 75 76 81 85 90 91 96 100 105 106 111 115 120 121 126 130 135 136 141 145 150 151 156 160 165 166 171 175 180 181 186 190 195 196 201 205 210 211 216 220 225 226 231 235 240 241 246 250 255 

Changing main:

int main() {
	ran r(17);
	for (int i : co9(1,288,&r)) { std::cout << i << ' '; }
	return 0;
}

Produces:

1 16 17 32 33 48 49 64 65 80 81 96 97 112 113 128 129 144 145 160 161 176 177 192 193 208 209 224 225 240 241 256 257 272 273 288 

Common Lisp

;;A macro was used to ensure that the filter is inlined.  
;;Larry Hignight.  Last updated on 7/3/2012.
(defmacro kaprekar-number-filter (n &optional (base 10))
  `(= (mod ,n (1- ,base)) (mod (* ,n ,n) (1- ,base))))
 
(defun test (&key (start 1) (stop 10000) (base 10) (collect t))
  (let ((count 0)
	(nums))
    (loop for i from start to stop do
	  (when (kaprekar-number-filter i base)
	    (if collect (push i nums))
	    (incf count)))
    (format t "~d potential Kaprekar numbers remain (~~~$% filtered out).~%"
	    count (* (/ (- stop count) stop) 100))
    (if collect (reverse nums))))

Output:

CL-USER> (test :stop 99)
22 potential Kaprekar numbers remain (~77.78% filtered out).
(1 9 10 18 19 27 28 36 37 45 ...)
CL-USER> (test :stop 10000 :collect nil)
2223 potential Kaprekar numbers remain (~77.77% filtered out).
NIL
CL-USER> (test :stop 1000000 :collect nil)
222223 potential Kaprekar numbers remain (~77.78% filtered out).
NIL
CL-USER> (test :stop 255 :base 16)
68 potential Kaprekar numbers remain (~73.33% filtered out).
(1 6 10 15 16 21 25 30 31 36 ...)
CL-USER> (test :stop 288 :base 17)
36 potential Kaprekar numbers remain (~87.50% filtered out).
(1 16 17 32 33 48 49 64 65 80 ...)

D

Translation of: Python

import std.stdio, std.algorithm, std.range;
 
uint[] castOut(in uint base=10, in uint start=1, in uint end=999999) {
    const ran = iota(base - 1)
                .filter!(x => x % (base - 1) == (x * x) % (base - 1))
                .array;
    auto x = start / (base - 1);
    immutable y = start % (base - 1);
 
    typeof(return) result;
    while (true) {
        foreach (immutable n; ran) {
            immutable k = (base - 1) * x + n;
            if (k < start)
                continue;
            if (k > end)
                return result;
            result ~= k;
        }
        x++;
    }
}
 
void main() {
    castOut(16, 1, 255).writeln;
    castOut(10, 1, 99).writeln;
    castOut(17, 1, 288).writeln;
}

Output (some newlines added):

[1, 6, 10, 15, 16, 21, 25, 30, 31, 36, 40, 45, 46, 51, 55, 60,
 61, 66, 70, 75, 76, 81, 85, 90, 91, 96, 100, 105, 106, 111, 115,
 120, 121, 126, 130, 135, 136, 141, 145, 150, 151, 156, 160, 165,
 166, 171, 175, 180, 181, 186, 190, 195, 196, 201, 205, 210, 211,
 216, 220, 225, 226, 231, 235, 240, 241, 246, 250, 255]
[1, 9, 10, 18, 19, 27, 28, 36, 37, 45, 46, 54, 55, 63, 64, 72, 73,
 81, 82, 90, 91, 99]
[1, 16, 17, 32, 33, 48, 49, 64, 65, 80, 81, 96, 97, 112, 113, 128,
 129, 144, 145, 160, 161, 176, 177, 192, 193, 208, 209, 224, 225,
 240, 241, 256, 257, 272, 273, 288]

Go

package main
 
import (
    "fmt"
    "log"
    "strconv"
)
 
// A casting out nines algorithm.
 
// Quoting from: http://mathforum.org/library/drmath/view/55926.html
/*
First, for any number we can get a single digit, which I will call the 
"check digit," by repeatedly adding the digits. That is, we add the 
digits of the number, then if there is more than one digit in the 
result we add its digits, and so on until there is only one digit 
left.
 
...
 
You may notice that when you add the digits of 6395, if you just 
ignore the 9, and the 6+3 = 9, you still end up with 5 as your check 
digit. This is because any 9's make no difference in the result. 
That's why the process is called "casting out" nines. Also, at any 
step in the process, you can add digits, not just at the end: to do 
8051647, I can say 8 + 5 = 13, which gives 4; plus 1 is 5, plus 6 is 
11, which gives 2, plus 4 is 6, plus 7 is 13 which gives 4. I never 
have to work with numbers bigger than 18.
*/
// The twist is that co9Peterson returns a function to do casting out nines
// in any specified base from 2 to 36.
func co9Peterson(base int) (cob func(string) (byte, error), err error) {
    if base < 2 || base > 36 {
        return nil, fmt.Errorf("co9Peterson: %d invalid base", base)
    }
    // addDigits adds two digits in the specified base.
    // People perfoming casting out nines by hand would usually have their
    // addition facts memorized.  In a program, a lookup table might be
    // analogous, but we expediently use features of the programming language
    // to add digits in the specified base.
    addDigits := func(a, b byte) (string, error) {
        ai, err := strconv.ParseInt(string(a), base, 64)
        if err != nil {
            return "", err
        }
        bi, err := strconv.ParseInt(string(b), base, 64)
        if err != nil {
            return "", err
        }
        return strconv.FormatInt(ai+bi, base), nil
    }
    // a '9' in the specified base.  that is, the greatest digit.
    s9 := strconv.FormatInt(int64(base-1), base)
    b9 := s9[0]
    // define result function.  The result function may return an error
    // if n is not a valid number in the specified base.
    cob = func(n string) (r byte, err error) {
        r = '0'
        for i := 0; i < len(n); i++ { // for each digit of the number
            d := n[i]
            switch {
            case d == b9: // if the digit is '9' of the base, cast it out
                continue
            // if the result so far is 0, the digit becomes the result
            case r == '0':
                r = d
                continue
            }
            // otherwise, add the new digit to the result digit
            s, err := addDigits(r, d)
            if err != nil {
                return 0, err
            }
            switch {
            case s == s9: // if the sum is "9" of the base, cast it out
                r = '0'
                continue
            // if the sum is a single digit, it becomes the result
            case len(s) == 1:
                r = s[0]
                continue
            }
            // otherwise, reduce this two digit intermediate result before
            // continuing.
            r, err = cob(s)
            if err != nil {
                return 0, err
            }
        }
        return
    }
    return
}
 
// Subset code required by task.  Given a base and a range specified with
// beginning and ending number in that base, return candidate Kaprekar numbers
// based on the observation that k%(base-1) must equal (k*k)%(base-1).
// For the % operation, rather than the language built-in operator, use
// the method of casting out nines, which in fact implements %(base-1).
func subset(base int, begin, end string) (s []string, err error) {
    // convert begin, end to native integer types for easier iteration
    begin64, err := strconv.ParseInt(begin, base, 64)
    if err != nil {
        return nil, fmt.Errorf("subset begin: %v", err)
    }
    end64, err := strconv.ParseInt(end, base, 64)
    if err != nil {
        return nil, fmt.Errorf("subset end: %v", err)
    }
    // generate casting out nines function for specified base
    cob, err := co9Peterson(base)
    if err != nil {
        return
    }
    for k := begin64; k <= end64; k++ {
        ks := strconv.FormatInt(k, base)
        rk, err := cob(ks)
        if err != nil { // assertion
            panic(err) // this would indicate a bug in subset
        }
        rk2, err := cob(strconv.FormatInt(k*k, base))
        if err != nil { // assertion
            panic(err) // this would indicate a bug in subset
        }
        // test for candidate Kaprekar number
        if rk == rk2 {
            s = append(s, ks)
        }
    }
    return
}
 
var testCases = []struct {
    base       int
    begin, end string
    kaprekar   []string
}{
    {10, "1", "100", []string{"1", "9", "45", "55", "99"}},
    {17, "10", "gg", []string{"3d", "d4", "gg"}},
}
 
func main() {
    for _, tc := range testCases {
        fmt.Printf("\nTest case base = %d, begin = %s, end = %s:\n",
            tc.base, tc.begin, tc.end)
        s, err := subset(tc.base, tc.begin, tc.end)
        if err != nil {
            log.Fatal(err)
        }
        fmt.Println("Subset:  ", s)
        fmt.Println("Kaprekar:", tc.kaprekar)
        sx := 0
        for _, k := range tc.kaprekar {
            for {
                if sx == len(s) {
                    fmt.Printf("Fail:", k, "not in subset")
                    return
                }
                if s[sx] == k {
                    sx++
                    break
                }
                sx++
            }
        }
        fmt.Println("Valid subset.")
    }
}

Output:

Test case base = 10, begin = 1, end = 100:
Subset:   [1 9 10 18 19 27 28 36 37 45 46 54 55 63 64 72 73 81 82 90 91 99 100]
Kaprekar: [1 9 45 55 99]
Valid subset.

Test case base = 17, begin = 10, end = gg:
Subset:   [10 1f 1g 2e 2f 3d 3e 4c 4d 5b 5c 6a 6b 79 7a 88 89 97 98 a6 a7 b5 b6
 c4 c5 d3 d4 e2 e3 f1 f2 g0 g1 gg]
Kaprekar: [3d d4 gg]
Valid subset.

J

This is an implementation of: "given two numbers which mark the beginning and end of a range of integers, and another number which denotes an integer base, return numbers from within the range where the number is equal (modulo the base minus 1) to its square". At the time of this writing, this task is a draft task and this description does not precisely match the task description on this page. Eventually, either the task description will change to match this implementation (which means this paragraph should be removed) or the task description will change to conflict with this implementation (so this entire section should be re-written).

castout=: 1 :0
   [: (#~  ] =&((m-1)&|) *:) <. + [: i. (+*)@-~
)

Example use:

   0 (10 castout) 100
0 1 9 10 18 19 27 28 36 37 45 46 54 55 63 64 72 73 81 82 90 91 99 100

Alternate implementation:

castout=: 1 :0
   [: (#~  0 = (m-1) | 0 _1 1&p.) <. + [: i. (+*)@-~
)

Note that about half of the code here is the code that implements "range of numbers". If we factor that out, and represent the desired values directly the code becomes much simpler:

   (#~ 0=9|0 _1 1&p.) i.101
0 1 9 10 18 19 27 28 36 37 45 46 54 55 63 64 72 73 81 82 90 91 99 100
   (#~  ] =&(9&|) *:) i. 101
0 1 9 10 18 19 27 28 36 37 45 46 54 55 63 64 72 73 81 82 90 91 99 100

And, of course, we can name parts of these expressions. For example:

   (#~  ] =&(co9=: 9&|) *:) i. 101
0 1 9 10 18 19 27 28 36 37 45 46 54 55 63 64 72 73 81 82 90 91 99 100

Or, if you prefer:

co9=: 9&|
   (#~  ] =&co9 *:) i. 101
0 1 9 10 18 19 27 28 36 37 45 46 54 55 63 64 72 73 81 82 90 91 99 100

PARI/GP

Translation of: C++

{base=10;
N=2;
c1=c2=0;
for(k=1,base^N-1,
  c1++;
  if (k%(base-1) == k^2%(base-1),
    c2++;
    print1(k" ")
  );
);
print("\nTrying "c2" numbers instead of "c1" numbers saves " 100.-(c2/c1)*100 "%")}
 

Produces:

1 9 10 18 19 27 28 36 37 45 46 54 55 63 64 72 73 81 82 90 91 99
Trying 22 numbers instead of 99 numbers saves 77.77777777777777777777777778%

Changing to: "base = 16;" produces:

1 6 10 15 16 21 25 30 31 36 40 45 46 51 55 60 61 66 70 75 76 81 85 90 91 96 100
105 106 111 115 120 121 126 130 135 136 141 145 150 151 156 160 165 166 171 175
180 181 186 190 195 196 201 205 210 211 216 220 225 226 231 235 240 241 246 250
255
Trying 68 numbers instead of 255 numbers saves 73.33333333333333333333333333%

Python

This works slightly differently, generating the "wierd" (as defined by Counting Out Nines) numbers which may be Kaprekar, rather than filtering all numbers in a range.

 
# Casting out Nines
#
# Nigel Galloway: June 27th., 2012,
#
def CastOut(Base=10, Start=1, End=999999):
  ran = [y for y in range(Base-1) if y%(Base-1) == (y*y)%(Base-1)]
  x,y = divmod(Start, Base-1)
  while True:
    for n in ran:
      k = (Base-1)*x + n
      if k < Start:
        continue
      if k > End:
        return
      yield k
    x += 1
 
for V in CastOut(Base=16,Start=1,End=255):
  print(V, end=' ')
 

Produces:

1 6 10 15 16 21 25 30 31 36 40 45 46 51 55 60 61 66 70 75 76 81 85 90 91 96 100 105 106 111 115 120 121 126 130 135 136 141 145 150 151 156 160 165 166 171 175 180 181 186 190 195 196 201 205 210 211 216 220 225 226 231 235 240 241 246 250 255 

CastOut(Base=10,Start=1,End=99), Produces:

1 9 10 18 19 27 28 36 37 45 46 54 55 63 64 72 73 81 82 90 91 99 

CastOut(Base=17,Start=1,End=288), Produces:

1 16 17 32 33 48 49 64 65 80 81 96 97 112 113 128 129 144 145 160 161 176 177 192 193 208 209 224 225 240 241 256 257 272 273 288 

Racket

 
#lang racket
(require math)
 
(define (digits n)
  (map (compose1 string->number string)
       (string->list (number->string n))))
 
(define (cast-out-nines n)
  (with-modulus 9
    (for/fold ([sum 0]) ([d (digits n)])
      (mod+ sum d))))
 

REXX

/*REXX program to demonstrate casting-out-nines (with Kaprekar numbers).*/
 
parse arg start stop base .            /*get the user args (if any).    */
if base=='' then base=10               /*use base ten if not specified. */
 
if start=='' then do                   /*use defaults if not specified. */
                  start=1
                  stop=1000
                  end
 
if stop=='' then stop=start            /*not specified?  Use the default*/
numbers=castOut(start,stop,base)       /*generate a list of numbers.    */
cast_out='cast-out-'||(base-1) "test"  /*build text shortcut.*/
 
say 'For' start "through" stop', the following passed the' cast_out":"
say numbers
say
 
q=stop-start+1
p=words(numbers)
pc=format(p/q*100,,2)/1 || '%'
 
say 'For' q "numbers," p 'passed the' cast_out "("pc') for base' base"."
if base\==10 then exit
 
Kaps=kaprekar(start,stop)              /*generate a list of Kaprekar #s.*/
say
say 'The Kaprekar numbers in the same range are:' Kaps
say
       do i=1 for words(Kaps);  x=word(Kaps,i)    /*verify 'em in list. */
       if wordpos(x,numbers)\==0 then iterate     /*OK so far ...       */
       say 'Kaprekar number' x "isn't in the numbers list."     /*oops! */
       exit                                       /*go spank the coder. */
       end
 
say 'All Kaprekar numbers are in the' cast_out "numbers list."      /*ok*/
exit                                   /*stick a fork in it, we're done.*/
 
/*──────────────────────────────────CASTOUT subroutine──────────────────*/
castOut:  procedure;  parse arg low,high,radix;  $=
 high=word(high low,1)                 /*use default of  LOW  for  HIGH.*/
radix=word(radix 10,1)                 /*use default ot   10  for RADIX.*/
niner=radix-1                          /*a fast way to use  RADIX - 1.  */
                  do j=low to high     /*traipse through the arg range. */
                  if j//niner==j*j//niner then $=$ j    /*pass the test?*/
                  end
return strip($)                        /*strip leading blank from result*/
 
/*──────────────────────────────────Kaprekar subroutine─────────────────*/
kaprekar:  procedure;  parse arg L,H;  $=;  if L<=1 then $=1
numeric digits max(10,2*length(limit**2))    /*insure enough digs for ².*/
                                       /*slow way to find Kaprekar nums.*/
  do j=max(2,L) to H;         s=j*j
      do k=1 for length(s)%2
      if j==left(s,k)+substr(s,k+1) then $=$ j     /*found a Kaprekar #.*/
      end   /*k*/
  end       /*j*/
 
return strip($)                        /*return the Kaprekar numbers.   */

output when using the default input

For 1 through 1000, the following passed the cast-out-9 test:
1 9 10 18 19 27 28 36 37 45 46 54 55 63 64 72 73 81 82 90 91 99 100 108 109 117
118 126 127 135 136 144 145 153 154 162 163 171 172 180 181 189 190 198 199 207
208 216 217 225 226 234 235 243 244 252 253 261 262 270 271 279 280 288 289 297
298 306 307 315 316 324 325 333 334 342 343 351 352 360 361 369 370 378 379 387
388 396 397 405 406 414 415 423 424 432 433 441 442 450 451 459 460 468 469 477
478 486 487 495 496 504 505 513 514 522 523 531 532 540 541 549 550 558 559 567
568 576 577 585 586 594 595 603 604 612 613 621 622 630 631 639 640 648 649 657
658 666 667 675 676 684 685 693 694 702 703 711 712 720 721 729 730 738 739 747
748 756 757 765 766 774 775 783 784 792 793 801 802 810 811 819 820 828 829 837
838 846 847 855 856 864 865 873 874 882 883 891 892 900 901 909 910 918 919 927
928 936 937 945 946 954 955 963 964 972 973 981 982 990 991 999 1000

For 1000 numbers, 223 passed the cast-out-9 test (22.3%) for base 10.

The Kaprekar numbers in the same range are: 1 9 45 55 99 297 703 999

All Kaprekar numbers are in the cast-out-9 test numbers list.

output when using the input of: 1 256 16

For 1 through 256, the following passed the cast-out-15 test:
1 6 10 15 16 21 25 30 31 36 40 45 46 51 55 60 61 66 70 75 76 81 85 90 91 96 100
105 106 111 115 120 121 126 130 135 136 141 145 150 151 156 160 165 166 171 175
180 181 186 190 195 196 201 205 210 211 216 220 225 226 231 235 240 241 246 250
255 256

For 256 numbers, 69 passed the cast-out-15 test (26.95%) for base 16.