C++: Casting Out Nines

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.

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;
}

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;
}

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;
}

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;
}

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

SOURCE

Content is available under GNU Free Documentation License 1.2.