login
Numbers n such that n^2 can be obtained from n by inserting internal (but not necessarily contiguous) digits.
8

%I #32 Nov 05 2016 12:53:02

%S 0,1,10,11,95,96,100,101,105,110,125,950,960,976,995,996,1000,1001,

%T 1005,1006,1010,1011,1021,1025,1026,1036,1046,1050,1100,1101,1105,

%U 1201,1205,1250,1276,1305,1316,1376,1405,9500,9505,9511,9525,9600,9605,9625

%N Numbers n such that n^2 can be obtained from n by inserting internal (but not necessarily contiguous) digits.

%C Contains A038444. In particular, the sequence is infinite. - _Robert Israel_, Oct 20 2016

%C If n is any positive term, then b_n(k) := n*10^k (k >= 0) is an infinite subsequence. - _Rick L. Shepherd_, Nov 01 2016

%C From Robert Israel's comment it follows that the subsequence of terms with no trailing zeros is also infinite (contains A000533). - _Rick L. Shepherd_, Nov 01 2016

%H Reinhard Zumkeller, <a href="/A046851/b046851.txt">Table of n, a(n) for n = 1..10000</a>

%e 110^2 = 12100 (insert "2" and "0" into "1_1_0").

%p IsSublist:= proc(a, b)

%p local i,bp,j;

%p bp:= b;

%p for i from 1 to nops(a) do

%p j:= ListTools:-Search(a[i],bp);

%p if j = 0 then return false fi;

%p bp:= bp[j+1..-1];

%p od;

%p true

%p end proc:

%p filter:= proc(n) local A,B;

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

%p B:= convert(n^2,base,10);

%p if not(A[1] = B[1] and A[-1] = B[-1]) then return false fi;

%p if nops(A) <= 2 then return true fi;

%p IsSublist(A[2..-2],B[2..-2])

%p end proc:

%p select(filter, [$0..10^4]); # _Robert Israel_, Oct 20 2016

%t id[n_]:=IntegerDigits[n];

%t insQ[n_]:=First[id[n]]==First[id[n^2]]&&Last[id[n]]==Last[id[n^2]];

%t sort[n_]:=Flatten/@Table[Position[id[n^2],id[n][[i]]],{i,1,Length[id[n]]}];

%t takeQ[n_]:=Module[{lst={First[sort[n][[1]]]}},

%t Do[

%t Do[

%t If[Last[lst]<sort[n][[i]][[h]],AppendTo[lst,sort[n][[i]][[h]]];Break[]],

%t {h,1,Length[sort[n][[i]]]}

%t ],

%t {i,2,Length[sort[n]]}

%t ];

%t If[Length[lst]==Length[id[n]]&&lst==Sort[lst],True,False]

%t ];

%t Select[Range[0,9625],insQ[#]&&takeQ[#]&] (* _Ivan N. Ianakiev_, Oct 19 2016 *)

%o (Haskell)

%o import Data.List (isInfixOf)

%o a046851 n = a046851_list !! (n-1)

%o a046851_list = filter chi a008851_list where

%o chi n = (x == y && xs `isSub` ys) where

%o x:xs = show $ div n 10

%o y:ys = show $ div (n^2) 10

%o isSub [] ys = True

%o isSub _ [] = False

%o isSub us'@(u:us) (v:vs)

%o | u == v = isSub us vs

%o | otherwise = isSub us' vs

%o -- _Reinhard Zumkeller_, Jul 27 2011

%Y Cf. A045953, A008851, A018834, A038444, A086457 (subsequence).

%K nonn,base,easy,nice

%O 1,3

%A _David W. Wilson_