login
k-digit positive numbers exactly one of whose substrings is divisible by k.
1

%I #34 Aug 16 2022 02:50:46

%S 1,2,3,4,5,6,7,8,9,21,23,25,27,29,41,43,45,47,49,61,63,65,67,69,81,83,

%T 85,87,89,101,104,107,110,111,112,113,114,115,116,117,118,119,122,125,

%U 128,131,134,137,140,141,142,143,144,145,146,147,148,149,152,155,158,161

%N k-digit positive numbers exactly one of whose substrings is divisible by k.

%C Inspired by the 413th problem of Project Euler (see link) where such a number is called "one-child number".

%C There are k*(k+1)/2 substrings. All are considered, even when some are duplicates as strings or as numbers (see the Example section). 0 is always divisible by k so any number with two or more 0 digits is not a term. - _Kevin Ryde_, Mar 08 2021

%C The 2-digit terms are odd.

%C The number of k-digit terms for k = 1, 2, 3 is respectively 9, 20, 360.

%C From _Robert Israel_, Mar 11 2021: (Start)

%C 5-digit terms are numbers starting with 5, and with no other digits 5 or 0.

%C There are no 10-digit terms. (End)

%H Robert Israel, <a href="/A342304/b342304.txt">Table of n, a(n) for n = 1..10000</a>

%H Project Euler, <a href="https://projecteuler.net/problem=413">Problem 413: One-child Numbers</a>.

%e 107 is a 3-digit one-child number since among its substrings 1, 0, 7, 10, 07, 107 only 0 is divisible by 3.

%e 222 is a 3-digit one-child number since among its substrings 2, 2, 2, 22, 22, 222 only 222 is divisible by 3.

%e 572 is not a 3-digit one-child number, since among its substrings 5, 7, 1, 57, 72, 572 both 57 and 72 are divisible by 3.

%e 616 is not a 3-digit one-child number, since among its substrings 6, 1, 6, 61, 16, 616 the two 6's are both divisible by 3.

%p filter:= proc(n) local L,d,i,j,k, ct, x;

%p L:= convert(n,base,10);

%p d:= nops(L);

%p ct:= 0:

%p for i from 1 to d do

%p for j from i to d do

%p x:= add(L[k]*10^(k-i),k=i..j);

%p if x mod d = 0 then ct:= ct+1; if ct = 2 then return false fi fi;

%p od od;

%p evalb(ct = 1)

%p end proc:

%p select(filter, [$1..200]); # _Robert Israel_, Mar 11 2021

%o (Python)

%o def ok(n):

%o s, c = str(n), 0

%o ss = (s[i:j] for i in range(len(s)) for j in range(i+1, len(s)+1))

%o for w in ss:

%o if int(w)%len(s) == 0: c += 1

%o if c == 2: return False

%o return n > 0 and c == 1

%o print([k for k in range(162) if ok(k)]) # _Michael S. Branicky_, Aug 15 2022

%Y Cf. A063527.

%K nonn,base

%O 1,2

%A _Bernard Schott_, Mar 08 2021