[Guest]

I got this as extra credit challenge question for algorithms class, I couldn't answer it completely, I'm not posting this to cheat though, I already submitted my answer but just wanted to share it...

We'll define the function S(n) to be the number of numbers from 0 to 10ⁿ that are both divisible by 23 and the sum of their digits is 23...

For example:

s(0)=s(1)=s(2)=s(3)=0

s(4)=20

s(5)=258

s(6)=2073

s(7)=12472

s(8)=61697

s(9)=263626

Calculate s(11¹²), (yes, you heard me, 10¹¹¹²);

Here's what I got (not full answer):

Despite the stupendous magnitude of the number, the sum of digits requirement is very limiting:

You can go over every possible set of numbers from 1-9 that sum up to 23, I had a recursive function which came up with 887 such sets:

11111111111111111111111

1111111111111111111112

111111111111111111113

111111111111111111122

11111111111111111114

11111111111111111123

1111111111111111115

11111111111111111222

1111111111111111124

1111111111111111133

111111111111111116

1111111111111111223

111111111111111125

111111111111111134

11111111111111117

1111111111111112222

111111111111111224

111111111111111233

11111111111111126

11111111111111135

11111111111111144

1111111111111118

111111111111112223

11111111111111225

11111111111111234

1111111111111127

11111111111111333

1111111111111136

1111111111111145

111111111111119

111111111111122222

11111111111112224

11111111111112233

1111111111111226

1111111111111235

1111111111111244

111111111111128

1111111111111334

111111111111137

111111111111146

111111111111155

11111111111122223

1111111111112225

1111111111112234

111111111111227

1111111111112333

111111111111236

111111111111245

11111111111129

111111111111335

111111111111344

11111111111138

11111111111147

11111111111156

11111111111222222

1111111111122224

1111111111122233

111111111112226

111111111112235

111111111112244

11111111111228

111111111112334

11111111111237

11111111111246

11111111111255

111111111113333

11111111111336

11111111111345

1111111111139

11111111111444

1111111111148

1111111111157

1111111111166

1111111111222223

111111111122225

111111111122234

11111111112227

111111111122333

11111111112236

11111111112245

1111111111229

11111111112335

11111111112344

1111111111238

1111111111247

1111111111256

11111111113334

1111111111337

1111111111346

1111111111355

1111111111445

111111111149

111111111158

111111111167

1111111112222222

111111111222224

111111111222233

11111111122226

11111111122235

11111111122244

1111111112228

11111111122334

1111111112237

1111111112246

1111111112255

11111111123333

1111111112336

1111111112345

111111111239

1111111112444

111111111248

111111111257

111111111266

1111111113335

1111111113344

111111111338

111111111347

111111111356

111111111446

111111111455

11111111159

11111111168

11111111177

111111112222223

11111111222225

11111111222234

1111111122227

11111111222333

1111111122236

1111111122245

111111112229

1111111122335

1111111122344

111111112238

111111112247

111111112256

1111111123334

111111112337

111111112346

111111112355

111111112445

11111111249

11111111258

11111111267

1111111133333

111111113336

111111113345

11111111339

111111113444

11111111348

11111111357

11111111366

11111111447

11111111456

11111111555

1111111169

1111111178

111111122222222

11111112222224

11111112222233

1111111222226

1111111222235

1111111222244

111111122228

1111111222334

111111122237

111111122246

111111122255

1111111223333

111111122336

111111122345

11111112239

111111122444

11111112248

11111112257

11111112266

111111123335

111111123344

11111112338

11111112347

11111112356

11111112446

11111112455

1111111259

1111111268

1111111277

111111133334

11111113337

11111113346

11111113355

11111113445

1111111349

1111111358

1111111367

11111114444

1111111448

1111111457

1111111466

1111111556

111111179

111111188

11111122222223

1111112222225

1111112222234

111111222227

1111112222333

111111222236

111111222245

11111122229

111111222335

111111222344

11111122238

11111122247

11111122256

111111223334

11111122337

11111122346

11111122355

11111122445

1111112249

1111112258

1111112267

111111233333

11111123336

11111123345

1111112339

11111123444

1111112348

1111112357

1111112366

1111112447

1111112456

1111112555

111111269

111111278

11111133335

11111133344

1111113338

1111113347

1111113356

1111113446

1111113455

111111359

111111368

111111377

1111114445

111111449

111111458

111111467

111111557

111111566

11111189

11111222222222

1111122222224

1111122222233

111112222226

111112222235

111112222244

11111222228

111112222334

11111222237

11111222246

11111222255

111112223333

11111222336

11111222345

1111122239

11111222444

1111122248

1111122257

1111122266

11111223335

11111223344

1111122338

1111122347

1111122356

1111122446

1111122455

111112259

111112268

111112277

11111233334

1111123337

1111123346

1111123355

1111123445

111112349

111112358

111112367

1111124444

111112448

111112457

111112466

111112556

11111279

11111288

11111333333

1111133336

1111133345

111113339

1111133444

111113348

111113357

111113366

111113447

111113456

111113555

11111369

11111378

111114446

111114455

11111459

11111468

11111477

11111558

11111567

11111666

1111199

1111222222223

111122222225

111122222234

11112222227

111122222333

11112222236

11112222245

1111222229

11112222335

11112222344

1111222238

1111222247

1111222256

11112223334

1111222337

1111222346

1111222355

1111222445

111122249

111122258

111122267

11112233333

1111223336

1111223345

111122339

1111223444

111122348

111122357

111122366

111122447

111122456

111122555

11112269

11112278

1111233335

1111233344

111123338

111123347

111123356

111123446

111123455

11112359

11112368

11112377

111124445

11112449

11112458

11112467

11112557

11112566

1111289

1111333334

111133337

111133346

111133355

111133445

11113349

11113358

11113367

111134444

11113448

11113457

11113466

11113556

1111379

1111388

11114447

11114456

11114555

1111469

1111478

1111559

1111568

1111577

1111667

1112222222222

111222222224

111222222233

11122222226

11122222235

11122222244

1112222228

11122222334

1112222237

1112222246

1112222255

11122223333

1112222336

1112222345

111222239

1112222444

111222248

111222257

111222266

1112223335

1112223344

111222338

111222347

111222356

111222446

111222455

11122259

11122268

11122277

1112233334

111223337

111223346

111223355

111223445

11122349

11122358

11122367

111224444

11122448

11122457

11122466

11122556

1112279

1112288

1112333333

111233336

111233345

11123339

111233444

11123348

11123357

11123366

11123447

11123456

11123555

1112369

1112378

11124446

11124455

1112459

1112468

1112477

1112558

1112567

1112666

111299

111333335

111333344

11133338

11133347

11133356

11133446

11133455

1113359

1113368

1113377

11134445

1113449

1113458

1113467

1113557

1113566

111389

11144444

1114448

1114457

1114466

1114556

111479

111488

1115555

111569

111578

111668

111677

112222222223

11222222225

11222222234

1122222227

11222222333

1122222236

1122222245

112222229

1122222335

1122222344

112222238

112222247

112222256

1122223334

112222337

112222346

112222355

112222445

11222249

11222258

11222267

1122233333

112223336

112223345

11222339

112223444

11222348

11222357

11222366

11222447

11222456

11222555

1122269

1122278

112233335

112233344

11223338

11223347

11223356

11223446

11223455

1122359

1122368

1122377

11224445

1122449

1122458

1122467

1122557

1122566

112289

112333334

11233337

11233346

11233355

11233445

1123349

1123358

1123367

11234444

1123448

1123457

1123466

1123556

112379

112388

1124447

1124456

1124555

112469

112478

112559

112568

112577

112667

113333333

11333336

11333345

1133339

11333444

1133348

1133357

1133366

1133447

1133456

1133555

113369

113378

1134446

1134455

113459

113468

113477

113558

113567

113666

11399

1144445

114449

114458

114467

114557

114566

11489

115556

11579

11588

11669

11678

11777

122222222222

12222222224

12222222233

1222222226

1222222235

1222222244

122222228

1222222334

122222237

122222246

122222255

1222223333

122222336

122222345

12222239

122222444

12222248

12222257

12222266

122223335

122223344

12222338

12222347

12222356

12222446

12222455

1222259

1222268

1222277

122233334

12223337

12223346

12223355

12223445

1222349

1222358

1222367

12224444

1222448

1222457

1222466

1222556

122279

122288

122333333

12233336

12233345

1223339

12233444

1223348

1223357

1223366

1223447

1223456

1223555

122369

122378

1224446

1224455

122459

122468

122477

122558

122567

122666

12299

12333335

12333344

1233338

1233347

1233356

1233446

1233455

123359

123368

123377

1234445

123449

123458

123467

123557

123566

12389

1244444

124448

124457

124466

124556

12479

12488

125555

12569

12578

12668

12677

13333334

1333337

1333346

1333355

1333445

133349

133358

133367

1334444

133448

133457

133466

133556

13379

13388

134447

134456

134555

13469

13478

13559

13568

13577

13667

144446

144455

14459

14468

14477

14558

14567

14666

1499

15557

15566

1589

1679

1688

1778

22222222223

2222222225

2222222234

222222227

2222222333

222222236

222222245

22222229

222222335

222222344

22222238

22222247

22222256

222223334

22222337

22222346

22222355

22222445

2222249

2222258

2222267

222233333

22223336

22223345

2222339

22223444

2222348

2222357

2222366

2222447

2222456

2222555

222269

222278

22233335

22233344

2223338

2223347

2223356

2223446

2223455

222359

222368

222377

2224445

222449

222458

222467

222557

222566

22289

22333334

2233337

2233346

2233355

2233445

223349

223358

223367

2234444

223448

223457

223466

223556

22379

22388

224447

224456

224555

22469

22478

22559

22568

22577

22667

23333333

2333336

2333345

233339

2333444

233348

233357

233366

233447

233456

233555

23369

23378

234446

234455

23459

23468

23477

23558

23567

23666

2399

244445

24449

24458

24467

24557

24566

2489

25556

2579

2588

2669

2678

2777

3333335

3333344

333338

333347

333356

333446

333455

33359

33368

33377

334445

33449

33458

33467

33557

33566

3389

344444

34448

34457

34466

34556

3479

3488

35555

3569

3578

3668

3677

44447

44456

44555

4469

4478

4559

4568

4577

4667

5558

5567

5666

599

689

779

788

Count = 887

Now you need to arrange them and add 0's, the numbers of diferent arrangements can be calculated using multinomial distribution, (the number of 0's is 10¹¹¹²-set.length())

I got that the number of numbers that their sum of digits is 23 is:

10277480826812889625905461378557875572691517481461831953754147520719499605119655242154450033684486429472192740396263445104872750535391605595298310825280700207409723892249248879229009387866039112298783504495013741138457018454771121439767243201237672648884843921745555

I didn't know how to tell which ones are divisible by 23 so I just divided the answer by 23 and hope the statistics work (that probably 1 out of every 23 numbers is divisible by 23)

446846992470125635908933103415559807508326847020079650163223805248673895874767619224106523203673323020530119147663628048037945675451808938926013514142639139452596690967358646923000408168088657056468848021522336571237261671946570497381184487010333593429775822684589

[Morningstar]

I got that the number of numbers that their sum of digits is 23 is:

10277480826812889625905461378557875572691517481461831953754147520719499605119655242154450033684486429472192740396263

4451048727505353916055952983108252807002074097238922492488792290093878660391122987835044950137411384570184547711214397672

43201237672648884843921745555

Why aren't there an infinite number of numbers whose digits sum to 23? For example, if we take 6 as the number the digits sum to, the number 123 has digit sum of 6 but so do 1023, 1230, 1203, 10023, and anything else obtained by adding 0's.

Edited November 23, 2011 by Morningstar

[Morningstar]

By the way, is that number actually divisible by 23? I suppose that there's a 1 in 23 chance that any number is divisible by 23, but I wonder if there's some mathematical connection...

Edited November 23, 2011 by Morningstar

[Guest]

Why aren't there an infinite number of numbers whose digits sum to 23? For example, if we take 6 as the number the digits sum to, the number 123 has digit sum of 6 but so do 1023, 1230, 1203, 10023, and anything else obtained by adding 0's.

The list is of raw numbers without the 0's, the 0's are added later...

If we're looking for s(100), and let's say there's the set {2,3,,9,9} then there are 100-5=95 0's to be added to that number, and if you calculate:

(100!)/((95!)*(1!)*(1!)*(2!))

That would be the number of numbers that are less than 10¹⁰⁰ that are comprised of one 2, one 3 two 9's and 95 0's...

Because there is a huge number of 0's in each set I had the program take care of it separately, to calculate it more efficiently...

In the original question we're looking for numbers that are less than 11¹² digits long..

Edited November 23, 2011 by Anza Power

[Morningstar]

I see.

[Guest]

I am not a programmer and know little about algorithms and coding. But here's an idea of how it could be done

Get all the numbers divisible by 23. Simple code n = 1 to 10^{11 ^12}; output X = 23n

Then get the sum of all digits of this output X. here's how:

For a number like 123456789, the sum of digits can easily be programmed (i guess, because its simple logic)

One's digit = get mod 10 for the number. this should give you the output 9 for our number

Ten's digit = get mod 100 for the number and subtract the one's digit. This should give you 80. Divide this result by 10. This gives you 8

Hundred's digit = get mod 1000 for the number and subtract the one's digit and ten times the 10s digit. Divide this result by 100

... and so on. You get the idea.

I am guessing that when you are writing a program, you can get the patterns in the program easily and do not need to write for each of the digits ;-)

Once you have all the digits, add them up.

Check if the sum is divisible by 23

Add up the number of times the sum is div by 23

The only problem is that the computer might take time to process this program as it involves too many numbers

[Quantum.Mechanic]

Anza, can you just convert your procedure to base 23? Anything ending in 0 (base23) is divisible by 23. Since the expansion by 0's is mechanical, this should be easier than actually doing the math, and more accurate than the statistical argument.

I'm also wondering if there's some number theoretic result that would help with determining this in the general case, for any base and any argument.

-QM

[CaptainEd]

Here's something that might help a little tiny bit.

10^22 = 1 (mod 23)

That means for any number x =10^22 * y + z

x (mod 23) = 10^22 * Y (mod 23) + z (mod 23)

since we can replace 10^22 with 1, this means

x (mod 23) = (y + z) (mod 23)

<...edited to remove false conclusion about removing 22 consecutive zeroes...>

Edited December 4, 2011 by CaptainEd

[CaptainEd]

Actually, I think it's better. it means that, to evaluate a number's divisibility by 23, you can separate a long number string by cutting it every 22 digits, starting at the right end, and add the residues mod 23.

[EventHorizon]

So, I started coding this up, but using smaller numbers so I could use ints in C (comments were written to explain what would be needed to get the right answer). It just kept getting nastier, so I stopped coding it. I'll just explain my approach.

So, as CaptainEd pointed out, the mod 23 value of powers of 10 repeat every 22nd one. This means we can mod 11^12 by 22. Since 11^12 is a multiple of 11 but not of 2, 11^12 (mod 22) = 11.

Each power of 10 from 10^0 up to 10^21 has a different mod 23 value. So for the whole 11^12 digits, (11^12 + 11) / 22 have a mod 23 value equal to 10^0 (mod 23) and same for up to 10^10 (mod 23), and (11^12 - 11) / 22 have a mod 23 value equal to 10^11 (mod 23) and the same for up to 10^21 (mod 23).

Since the sum of the digits needs to be 23, we must distribute these 23 increments among the 11^12 digits (a max of 9 per digit, so as not to overflow to the next digit). Since we need to make sure the number is ultimately divisible by 23 and the digits sum to 23, we need to find all distributions of the 23 increments among the 22 possible mod 23 values for powers of 10 that sum to 0 (mod 23).

This will be a fairly simple iterative or recursive enumeration. In my code I enforced a decreasing order to ensure uniqueness.

For each distribution that sums to 0 (mod 23) you need to then see how the increments are distributed among the (11^12 + 11)/22 or (11^12 - 11)/22 digits with that mod 23 value. This is not a simple function, which is where I stopped coding it. This is equivalent to finding all the cardinality k subsets of a multiset (searched online for a simple formula for a while, and if anyone finds one let me know).

I'd approach it by finding all the partitions of the number of increments but restrict the largest partitions to a value of 9, and then find all the ways of assigning these partitions to the (11^12 + 11)/22 or (11^12 - 11)/22 digits (careful to avoid repetitions, like when the partition has 2 equivalent groups). Once you know the number of possibilities of assigning the increments for each mod 23 value, multiply them all. Sum this product for all possible distributions of the increments, and this is your answer. Yeah, nasty...

Example:

11 of 10^0 (mod 23) (=1), 10 of 10^11 (mod 23) (=22), and 2 of 10^3 (mod 23) (=11)

11*1+10*22+2*11=253= 23*11 = 0 (mod 23) so we proceed to finding all partitions for each mod 23 value

So find all partitions of the number 11 and count all ways to assign them to the (11^12 + 11)/22 digits with a mod 23 value of 1.

Do the same for the 10 increments with the mod 23 value of 22 and the 2 for the mod 23 value of 11, then multiply them together.

This should be the count of all numbers that have a digit sum of 11 for the 0 (mod 22) digits, a 10 for the 11 (mod 22) digits, and 2 for the 3 (mod 22) digits.

Sum over all possible distributions of increments for final answer.

Anyone see errors or a way to simplify? Or have questions? I'm sure this is rather hard to read through.

[Guest]

We can go for a particular number of digits at a time, say 3.

We need to find the number of numbers of 3 digit, whose sum comes down to 2 digit. i.e: X1+X2+X3 = {10,11,12,....,99}(say Z) where number is X1X2X3.

Suppose number of numbers of 3 digits with sum of there digits is P.

Now, since we need to add the digits of Z i.e. : Z = Z1Z2, then Z1+Z2 = {1,2,...,9}, say Y

So out of P digit, probability of occurence of a number Z, whose sum is 5 is 1/9.

2 digit numbers with sum 5 are:

14, 23, 32, 41, 50

So, probability that if sum, Y, is 5, Z is 23 is: 1/5.

P(Z) = 1/9 and P(Y) = 1/5 and P is the number of numbers, the sum of whose digits is a 2 digit number(i.e. - lie within range of(10,11,12,...99)

So, we have, for 3 digit numbers:

Probability that sum of digits of a number is 23, say P(S23) => P(Z) * P(Y) * P

Again, probability that a number will be divisible by 23 P(D23) = 1/23.

So, for a 3 digit number, required answer would be : P(A23) = P(S23) * P(D23).

This can be extended to any number of digits, but at later point of time, it will become a tiry process.

Anyone, if they can simplify it or find any errors? At times, it may be little hard to understand, sorry for this