#include "stdafx.h"
#include <conio.h>
#include <math.h>
typedef unsigned long long ull;

const	ull radix=10;
void main(void)
{
	int count_k_numbers=0;
	ull k_numbers_sum=0;
	ull k=9; //first number
	ull limit=radix;
	printf("n          k             k*k     k*k left    k*k right\n\n");
	for(ull digits_count=1 ; digits_count<=6 ; digits_count++)//[9..999999]
	{
		for( ;k<limit; k++)//[9], [10..99], [100..999],...,[100000..999999]			
		{
			ull k_square=k*k;
			ull k_square_save=k_square; //k_square will be destroyed
			//build k_square "right" that have digits_count digits 
			ull right=0;
			ull tmp=1;
			for(ull j=0 ; j<digits_count ; j++)
			{
				right=right+(k_square%radix)*tmp;
				k_square/=radix;
				tmp*=radix;
			}
			//build k_square "left" with the rest of the digits
			ull left=0;
			tmp=1;
			while(k_square!=0)
			{
				left=left+(k_square%radix)*tmp;
				k_square/=radix;
				tmp*=radix;
			}
			if(k==left+right)//test for k-number
			{
				printf("%-4d %7llu %15llu %12llu %12llu\n",++count_k_numbers,k,k_square_save,left,right);
				k_numbers_sum+=k; //found
			}
		}
		limit*=radix;
	}
	printf("\nThe sum of the k numbers is %llu",k_numbers_sum);

	_getch();
}
/*
n          k             k*k     k*k left    k*k right

1          9              81            8            1
2         45            2025           20           25
3         55            3025           30           25
4         99            9801           98            1
5        297           88209           88          209
6        703          494209          494          209
7        999          998001          998            1
8       2223         4941729          494         1729
9       2728         7441984          744         1984
10      4950        24502500         2450         2500
11      5050        25502500         2550         2500
12      7272        52881984         5288         1984
13      7777        60481729         6048         1729
14      9999        99980001         9998            1
15     17344       300814336         3008        14336
16     22222       493817284         4938        17284
17     77778      6049417284        60494        17284
18     82656      6832014336        68320        14336
19     95121      9048004641        90480         4641
20     99999      9999800001        99998            1
21    142857     20408122449        20408       122449
22    148149     21948126201        21948       126201
23    181819     33058148761        33058       148761
24    187110     35010152100        35010       152100
25    208495     43470165025        43470       165025
26    318682    101558217124       101558       217124
27    329967    108878221089       108878       221089
28    351352    123448227904       123448       227904
29    356643    127194229449       127194       229449
30    390313    152344237969       152344       237969
31    461539    213018248521       213018       248521
32    466830    217930248900       217930       248900
33    499500    249500250000       249500       250000
34    500500    250500250000       250500       250000
35    533170    284270248900       284270       248900
36    538461    289940248521       289940       248521
37    609687    371718237969       371718       237969
38    643357    413908229449       413908       229449
39    648648    420744227904       420744       227904
40    670033    448944221089       448944       221089
41    681318    464194217124       464194       217124
42    791505    626480165025       626480       165025
43    812890    660790152100       660790       152100
44    818181    669420148761       669420       148761
45    851851    725650126201       725650       126201
46    857143    734694122449       734694       122449
47    961038    923594037444       923594        37444
48    994708    989444005264       989444         5264
49    999999    999998000001       999998            1

The sum of the k numbers is 16393071
*/